Michael Claßen wrote:
I have to say that it puzzles me that there seems to be so little demand for a precise way of dealing with something like Z-polytopes. I have met a number of people already who are looking for the same thing as I am, but apparently, they are either not complaining or just not aware of this discussion.
Hi Michael,
complaining would not be very useful :-)
I propose you to start from the beginning. But this time, let us avoid anything that is not precisely defined.
My understanding is that you are interested in Z-polytopes. A polytope is a bounded, convex polyhedron, right?
And a Z-polytope is the intersection between a polytope and an integer lattice, right? (Note: in the PPL "integer lattices" are called "integral grids".)
The PPL provides a way to "combine" a Grid (which can represent any integer lattice), with a C_Polyhedron (which can represent any polytope). But the combination is loose, because the tight integration is computationally intractable.
Now, what operations do you require? I guess you need to know if a Z-polytope is empty, right? This requires to answer, for a given polytope P in R^n described by a system of constraints with rational coefficients, the question:
Is P intersected with Z^n empty?
We currently use a standard, branch-and-bound mixed integer programming optimizer: it may fail to terminate, it may be ridiculously expensive. Can we do better? We got in touch with three leading experts in the field. Two did not bother to reply. *The* leading expert told us that "[Lenstra's algorithm, the algorithm of Gr"otschel, Lov'asz and Schrijver, and the algorithm of Lov'asz and Scarf] are essentially theoretical. I don't know of any implementations." If you know the algorithm we should use, please share.
If we want the tight integration between C_Polyhedron and Grid, we also need to compute a representation of the "integer hull" of P, that is, the convex polyhedral hull of P intersected with Z^n. Which cutting plane algorithm(s) should we use? So far, we got no answer from the experts we contacted. Do you know the answer?
Perhaps I have misunderstood what you mean by a "precise way of dealing with something like Z-polytopes"? Please let us know. Cheers,
Roberto