Page 1 of 1

### Finding integer vertices in an MILP

Posted: 03 Nov 2021, 12:32
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

### Re: Finding integer vertices in an MILP

Posted: 03 Nov 2021, 15:22
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.

### Re: Finding integer vertices in an MILP

Posted: 05 Nov 2021, 11:43
Dear Dr. Paffenholz,

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

### Re: Finding integer vertices in an MILP

Posted: 05 Nov 2021, 14:11
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 ```

### Re: Finding integer vertices in an MILP

Posted: 05 Nov 2021, 20:13
Dear Dr. Paffenholz,