[PPL-devel] Integer projection

[Enea Zaffanella]

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.