## Finding integer vertices in an MILP

General discussion on polymake goes here.
Abbas Omidi
Posts: 11
Joined: 26 Sep 2021, 12:46

### Finding integer vertices in an MILP

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
Developer
Posts: 212
Joined: 24 Dec 2010, 13:47

### Re: Finding integer vertices in an MILP

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 Posts: 11 Joined: 26 Sep 2021, 12:46 ### Re: Finding integer vertices in an MILP 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 Developer Posts: 212 Joined: 24 Dec 2010, 13:47 ### Re: Finding integer vertices in an MILP 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
Posts: 11
Joined: 26 Sep 2021, 12:46

### Re: Finding integer vertices in an MILP

Dear Dr. Paffenholz,