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

Questions and problems about using polymake go here.
Abbas Omidi
Posts: 11
Joined: 26 Sep 2021, 12:46

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

Postby Abbas Omidi » 22 Aug 2022, 08:01

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

User avatar
joswig
Main Author
Posts: 287
Joined: 24 Dec 2010, 11:10

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

Postby joswig » 22 Aug 2022, 09:47

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
Posts: 11
Joined: 26 Sep 2021, 12:46

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

Postby Abbas Omidi » 23 Aug 2022, 10:26

Dear Prof. Joswig,

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

Best regards
Abbas

Abbas Omidi
Posts: 11
Joined: 26 Sep 2021, 12:46

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

Postby Abbas Omidi » 23 Aug 2022, 12:06

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

User avatar
joswig
Main Author
Posts: 287
Joined: 24 Dec 2010, 11:10

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

Postby joswig » 06 Sep 2022, 09:39

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
Posts: 11
Joined: 26 Sep 2021, 12:46

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

Postby Abbas Omidi » 16 Sep 2022, 22:56

Dear Prof.

Many thanks for the informative details.

Best regards
Abbas


Return to “Helpdesk”