How we can get the integer hull facets by using Polymake?

[Abbas Omidi]

Dear support team,

I hope you are doing well. I am working on a simple polyhedron to separate a specific cut. The polyhedron defines as P = {4x1+x2<=28, x1+4x2<=27, x1-x2<=1, x1>=0, x2>=0}. I computed the vertex and lattice points of the polyhedron by:

Code: Select all

$p = new Polytope(INEQUALITIES=>[[28,-4,-1],[27,-1,-4],[1,-1,1],[0,1,0],[0,0,1]]); $p->VERTICES; $p->LATTICE_POINTS;

Now, I would like to show the facets of the convex hull and also the integer convex hull. I tried:

Code: Select all

$p->FACETS;

and the results are:

Code: Select all

28 -4 -1 27 -1 -4 1 -1 1 0 1 0 0 0 1

By investigation, we can show that the facet-inducing valid inequalities describing conv(S) = conv(P ∩ Z2) are:

Code: Select all

x1+2x2<=15 x1-x2<=1 x1<=5 x2<=6 x1>=0 x2>=0

My questions are:
1) What is the difference between the first generated facets and the second one? (It seems it is related to the inequalities that shape the integer convex hull).
2) How we can get the facets as same as the second set by using Polymake?

Best regards
Abbas

[joswig]

The first description is the facet description of your input. Here it is essentially the same as your input, as the given inequalities proved to be irredundant.

For an overview of how to apply polymake in the context of integer linear programming, including integer hulls, see this tutorial.
More details about the relevant algorithms, implementations, and software components: https://doi.org/10.1007/s12532-016-0104-z.

Your example:

Code: Select all

polytope > $p = new Polytope(INEQUALITIES=>[[28,-4,-1],[27,-1,-4],[1,-1,1],[0,1,0],[0,0,1]]); polytope > $q = integer_hull($p); polytope > print $q->FACETS; 6 0 -1 1 -1 1 0 1 0 0 0 1 5 -1 0 15 -1 -2

[Abbas Omidi]

Dear Prof. Joswig,

Many thanks for the explanation. This is exactly what I was looking for.

Best regards
Abbas

[Abbas Omidi]

Dear Prof. Joswig,

Following up on the link you provided in the tutorial, I am trying to separate the CG-cuts on a specific polyhedron. It seems to work well and cuts the floating points from the problem space. (All vertices would be lattice points). Would you please, are there any related documents on how Poymake separates the CG-cuts?

Regards
Abbas

[joswig]

The code of the client gc_closure can be viewed on github.

The algorithm is described in §22.3 and §23.1 of Schrijver's book on integer and linear programming (Wiley 1986).

[Abbas Omidi]

Dear Prof.

Many thanks for the informative details.

Best regards
Abbas