[PPL-devel] integer versus rational solutions

[Michael Classen]

Hello Roberto,

I just wanted to ask if there are any new developments in this issue
of integral polytopes? My colleague Armin Groesslinger will visit me
next week and it would be great to to know the current status for any
discussions with him. :-)

best regards,
Michael

On Fri, Jul 17, 2009 at 4:48 PM, Michael
Classen<michael.classen at uni-passau.de> wrote:
> 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
>