[PPL-devel] integer versus rational solutions
bagnara at cs.unipr.it
Mon Jul 13 17:26:29 CEST 2009
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.
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.
Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
mailto:bagnara at cs.unipr.it
More information about the PPL-devel