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 Bagnarabagnara@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