Finding integer vertices in an MILP

[Abbas Omidi]

Dear support team,

I am trying to implement a decomposition algorithm and I have to work with extreme points of the MILP. As I asked some questions about defining polyhedron, I have tried to use the same approach to find integer vertices, but I am failing to do that. Also, I am working on lattice and lattice points too. What I am looking for is, in an MILP problem (actually, the defined polyhedron) the integer vertices are $\{(0,0),(4,0),(2,1),(0,1)\}$ respectively. when I am solving the problem the Polymake shows vertices of the linear relaxation of the MILP and it is different from what I am looking for. The syntax I have used is:
***
* without upper bound
$p = new Polytope(INEQUALITIES=>[[18,-4,-9],[4,2,-4],[0,1,0],[0,0,1]]);
***
***
* with upper bound
$p = new Polytope(INEQUALITIES=>[[18,-4,-9],[4,2,-4],[0,1,0],[0,0,1],[-9,-1,0],[-9,0,-1]]);
***
In the first attempt, I got the linear relaxation vertices while, in the second, it seems, the Polymake waits for another argument.
I was wondering if, how can I define/find the integer vertices of the MILP polyhedron?

Regards
Abbas

[paffenholz]

Yor can compute the integer hull of a polyhedron with the function integer_hull and then ask for the vertices:

Code: Select all

$q=integer_hull($p); print $q->VERTICES; 1 0 0 1 0 1 1 2 1 1 4 0

Note however, that this internally computes a representation of all integer points in the polyhedron. There is no significantly more efficient algorithm to compute the integer hull of a polyhedron.

Your second polytope is empty. The last two inequalities demand that all coordinates are less or equal to -9, but already the first polytope, which is a relaxation of the second, lives in the positive orthant.

[Abbas Omidi]

Dear Dr. Paffenholz,

Many thanks for your prompt reply.
I am aware of, the finding all of the integer vertices of a MILP problem needs to consume a lot of time and effort, but for a trivial problem, it is very helpful for understanding the problem structure. W.r.t the above problem, As it has four vertices, indeed has eight integer extreme points. Is there any way to find all of the extreme points of the problem?

Regards
Abbas

[paffenholz]

I am not sure what you mean by "extreme point". Can you please give a definition?

There are eight integral points contained in the polytope, which you can compute via

Code: Select all

print $p->LATTICE_POINTS; 1 0 0 1 0 1 1 1 0 1 1 1 1 2 0 1 2 1 1 3 0 1 4 0

Six of them are on the boundary:

Code: Select all

print $p->BOUNDARY_LATTICE_POINTS; 1 0 0 1 0 1 1 1 0 1 2 0 1 3 0 1 4 0

[Abbas Omidi]

Dear Dr. Paffenholz,

Many thanks for your comments.
Actually, I mean by extreme points is integer vertices (integer convex hull) and the provided output of the function is what exactly I was looking for. But the thing that was strange is, I could not get the results from the mentioned function last time and I asked this question!!
I will check it again and come back to you if I have any issues.
Thanks once again.

Regards
Abbas