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.