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.