[PPL-devel] integer versus rational solutions

[Roberto Bagnara]

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

-- 
Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bagnara at cs.unipr.it