how to define integer polytope by matrix representation

[Abbas Omidi]

Dear support team,

First, thanks for your useful tool. I am trying to define a polyhedron (actually, integer polytope) by using "https://shell.polymake.org/".
I would like to represent the polyhedron of the GAP (generalized assignment problem) that is defined by the following constraints:
// CPLEX lp format
Minimize
obj: x1
Subject To
e1: x1 - 9 b2 - 2 b3 - b4 - 2 b5 - 3 b6 - 8 b7 = 0
e2: b2 + b3 = 1
e3: b4 + b5 = 1
e4: b6 + b7 = 1
e5: 6 b2 + 7 b4 + 9 b6 <= 13
e6: 8 b3 + 5 b5 + 6 b7 <= 11
Bounds
x1 Free
0 <= b2 <= 1
0 <= b3 <= 1
0 <= b4 <= 1
0 <= b5 <= 1
0 <= b6 <= 1
0 <= b7 <= 1
Binaries
b2 b3 b4 b5 b6 b7
End
//

What I am trying to do is based on the matrix generation form as:
$inequalities=new Matrix<Integer>([
[1,-1,-1,0,0,0,0],
[1,0,0,-1,-1,0,0],
[1,0,0,0,0,-1,-1],
[13,-6,0,-7,0,-9,0],
[11,0,-8,0,-5,0,-6],
[-1,1,1,0,0,0,0],
[-1,0,0,1,1,0,0],
[-1,0,0,0,0,1,1]]);
$p=new Polytope<Rational>(INEQUALITIES=>$inequalities);
print_constraints($p->INEQUALITIES);

It seems to work but I was wondering if,
1- Is there any simple way to define equality constraints instead of their corresponding inequalities?
2- How we can invoke the extreme points of the polyhedron? (is it: print $p->VERTICES;)
3- As my problem is an optimization program (BIP) what is the best way to use the "$f = lp2poly" method inside of the "https://shell.polymake.org/"? if not, is there any alternative? (to clear: is there any way to define a MILP by the above matrix form?)

Best regards
Abbas

[joswig]

You can specify polyhedra in terms of INEQUALITIES and EQUATIONS.
Asking for VERTICES then triggers a dual convex hull computation.

Please see tutorial.

The web version of polymake runs in a sandbox. So, by design, you cannot read from or write to files.

[Abbas Omidi]

Dear support team,

Thanks for your helpful answer. I have tried this and works well, but I have an issue with calculating the vertices by defining the polyhedron based on both methods. Let's say, in the first attempt, I define the problem by the following method:
//
$p = new Polytope(INEQUALITIES=>[[13,-6,0,-7,0,-9,0],[11,0,-8,0,-5,0,-6]],EQUATIONS=>[[-1,1,1,0,0,0,0],[-1,0,0,1,1,0,0],[-1,0,0,0,0,1,1]]);
//
When the vertices are being invoked it shows:
//
1 -1/4 5/4 1 0 5/6 1/6
0 1 -1 0 0 -2/3 2/3
0 1 -1 0 0 -4/3 4/3
//
At the second attempt, I define the problem as follows:
//
$inequalities=new Matrix<Integer>([[1,-1,-1,0,0,0,0],[1,0,0,-1,-1,0,0],[1,0,0,0,0,-1,-1],[13,-6,0,-7,0,-9,0],[11,0,-8,0,-5,0,-6],[-1,1,1,0,0,0,0],[-1,0,0,1,1,0,0],[-1,0,0,0,0,1,1]]);
//
With this definition the vertices are:
//
1 -9/26 35/26 28/13 -15/13 0 1
0 1 -1 -8/5 8/5 0 0
0 1 -1 -6/7 6/7 0 0
//
As both definitions came from a specific problem (I try both in optimization software and the results are the same), I thought the vertices should be the same too, but they are different.
I would be appreciated where I am doing something wrong or it is reasonable that these results?

Best regards
Abbas

[joswig]

Your example has a lineality space of positive dimension.

Code: Select all

polytope > $p = new Polytope(INEQUALITIES=>[[13,-6,0,-7,0,-9,0],[11,0,-8,0,-5,0,-6]],EQUATIONS=>[[-1,1,1,0,0,0,0],[-1,0,0,1,1,0,0],[-1,0,0,0,0,1,1]]); polytope > print $p->VERTICES; 1 -1/4 5/4 1 0 5/6 1/6 0 1 -1 0 0 -2/3 2/3 0 1 -1 0 0 -4/3 4/3 polytope > print $p->LINEALITY_SPACE; 0 -3/26 3/26 18/13 -18/13 -1 1

Therefore the coordinates for VERTICES are only defined up modulo that one dimensional subspace.

So your polyhedron has one vertex, two rays + a one-dimensional linear subspace. polymake's perspective is that this is a triangle, from a combinatorial point of view. The VERTICES list some representatives. See here for details on polymake's semantics when it comes to polytopes and unbounded polyhedra.

[Abbas Omidi]

Dear Prof. Joswig,

Many thanks for your detailed explanation. As I am pretty new in this field, what you answered is very interesting to me.
Would you say please, how we can find the related documents about the interpretation of the vertices method? I mean, how can I find the number of vertices, rays, or other related fields based on the output of the method as you mentioned.
If I understand, is it possible to say that both method's outputs are correct and the difference came back to the combinatorial behavior of the model?

Best regards
Abbas

[opfer]

I would like to add that it seems you forgot to add the bounds of your binary variables to the polytope. If you add them and then calculate the lattice points, you should observe only two integer feasible solutions. So your problem and its solution space is rather trivial.

Best regards,
Thomas

[Abbas Omidi]

Dear Thomas,

Many thanks for your clarifying where I was doing wrong. It now makes sense as the two different methods (matrix & in/eq form) could produce the same solution. Would you say places, where I can find the related documents about what Dr. Joswig mentioned for the polyhedron specifications? (it is very interesting to me).

So your polyhedron has one vertex, two rays + a one-dimensional linear subspace.

Best regards
Abbas