# [PPL-devel] integer versus rational solutions

Roberto Bagnara 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.

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
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.

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

```