[PPL-devel] integer versus rational solutions

[Michael Classen]

Hello Roberto,

I hope I can clear up some of the issues in this mail. I apologize
ahead if there is still some imprecision in my explanations.

On Mon, Jul 13, 2009 at 5:26 PM, Roberto Bagnara<bagnara at cs.unipr.it> wrote:
> Hi Michael,
>
> complaining would not be very useful :-)

Indeed, I have nothing to complain about, I am very thankful for your
fast responses and help. :-)

> I propose you to start from the beginning.  But this time, let us
> avoid anything that is not precisely defined.

Yes, agreed.

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

Yes, agreed.
>
> 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.

Ok, I discussed this topic with my colleague Armin Größlinger. It
seems that what you mean by "tight integration" is the problem of
finding the minimal containing polytope that contains all the points
on the integer lattice.

However, we do NOT need this minimal integer hull of our polytope. For
our purposes, it is enough to get any description of the set of
integer points that is contained in the intersection of the polytope
and our grid/lattice. So, the polytope containing these integer points
may be slightly too large, it does not have to be minimal. I think
this makes finding a representation much easier.

> Now, what operations do you require?

We require test for empty, intersection, union and a difference-operator.

1) test for empty z-polytopes should be fairly simple using PIPlib (see below).
2) intersection should also be relatively easy to implement by
performing intersection on the polytope and grid
3) union should also be easy to represent in form of a list of
Z-polytopes (if a disjoint union is needed, we need a difference
operator -> 4)
4) a difference operator seems to be the most complicated operation to
implement. It should be possible to compute a complement of a given
polytope and the corresponding grid in form of a union of polytopes
and a finite set (or list) of complement grids. This representation
could get extremely large, but it should be managable if the result is
again intersected with our original polytope and grid.  So we compute:
A \ B = A 'intersect' (complement B)

Armin told me that he started implementing these functions in our
HSLooPo framework already, but there seems to be some problem related
to handling parameters in a difference operator.

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

yes.

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

I discussed this problem with Armin. We think that it is possible to
use PIP lib for testing for the empty set in this case. The algorithm
in PIP is of exponential complexity, if I remember correctly, but at
least it is guaranteed to terminate and in practice, I think it is
quite feasable. As far as I know, there are already attempts to
integrate PIP into PPL, so this seems to not be a big problem.

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

I think this can be answered by the 2 points I mentioned above:
1) we don't need a "minimal" representation of our polytope holding
our integer points, only a representation that holds all points
2) we can use PIP for test for empty sets

>
> Perhaps I have misunderstood what you mean by a "precise way of
> dealing with something like Z-polytopes"?  Please let us know.

What I mean is: we need some description that can give us the exact
set of all integral points contained in the Z-polytope. But as I
described above, this representation does not have to be minimal.

> Cheers,
>
>   Roberto

I hope I could clear up this misunderstanding, but I am sure we still
have some open points to discuss. Will you be participating in one of
those weekly telephone conferences of the Graphite project?

best regards,
Michael