[PPL-devel] Integer projection

[Enea Zaffanella]

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.