Dear PPL developers,
What would you think is the most sensible way to compute the convex hull of all the integer points in a given polyhedron?
drop_some_non_integer_points() seems to be quite close but the description reads like it might not always compute exactly this.
Thank you in advance, and also for this very nice library.
Cheers,
Didier
-- Dr. Didier Lime Maître de Conférences IRCCyN / École Centrale de Nantes Nantes, France
Il 29/09/2011 18:15, Didier Lime ha scritto:
Dear PPL developers,
What would you think is the most sensible way to compute the convex hull of all the integer points in a given polyhedron?
drop_some_non_integer_points() seems to be quite close but the description reads like it might not always compute exactly this.
Thank you in advance, and also for this very nice library.
Cheers,
Didier
Hello Didier.
I am afraid I don't have an answer to your question. As far as I can tell, unless some strong assumptions are made (e.g., fixed-and-low space dimension or fixed shape polyhedra), computing the integer hull of a rational polyhedron is really a tough problem.
Your observation is correct: as explained in the PPL documentation, drop_some_non_integer_points() will *NOT* generally compute the integer convex hull of the input polyhedron; it can be used to obtain an over-approximation of the integer hull which improves upon the rational hull.
Regards, Enea Zaffanella.
Hello Enea,
[...] I am afraid I don't have an answer to your question. As far as I can tell, unless some strong assumptions are made (e.g., fixed-and-low space dimension or fixed shape polyhedra), computing the integer hull of a rational polyhedron is really a tough problem.
Thanks for the quick answer. I suspected as much.
Do you know if it makes it easier that the polyhedron whose integer hull I want is obtained as the intersection between an "integer" polyhedron (it is its own integer hull) and a simple linear constraint?
Regards,
Didier
Il 05/10/2011 11:06, Didier Lime ha scritto:
Hello Enea,
[...] I am afraid I don't have an answer to your question. As far as I can tell, unless some strong assumptions are made (e.g., fixed-and-low space dimension or fixed shape polyhedra), computing the integer hull of a rational polyhedron is really a tough problem.
Thanks for the quick answer. I suspected as much.
Do you know if it makes it easier that the polyhedron whose integer hull I want is obtained as the intersection between an "integer" polyhedron (it is its own integer hull) and a simple linear constraint?
Regards,
Didier
Never really thought about it.
It could be simpler, but I wouldn't be so confident it is going to be much simpler. If it was really simpler, then we would immediately obtain a "simple" incremental algorithm for the construction of an integer polyhedron ... wouldn't we?
My first impression is that the addition of even a single linear constraint to an integer polytope could non-trivially affect all the facets that are intersected by the new constraint. "Non-trivially" means that each affected facet may or may not be a facet of the resulting polytope and, more importantly, the intersection of the constraint with each of these facets could generate many new facets.
But this is just a first (and probably shallow) impression ... have you considered the issue in some greater depth?
Regards, Enea.
participants (2)
-
Didier Lime -
Enea Zaffanella