Function gc_closure

Questions and problems about using polymake go here.
Peter Bezdek
Posts: 3
Joined: 11 Feb 2015, 09:49

Function gc_closure

Postby Peter Bezdek » 11 Feb 2015, 15:33

Hello again,

I am using function gc_closure on rational polytope and on following polytope (2D with 4 vertices)

Code: Select all

$q=new Polytope<Rational>(VERTICES=>[[1,1,0],[1,2,15/10],[1,24/10,15/10],[1,3,0]],LINEALITY_SPACE=>[[]]); $qq=gc_closure($q); print $qq->VERTICES;
it returns correct gomory chvatal closure.

Code: Select all

1 1 0 1 3 0 1 2 1
When called on slightly modified polytope (3rd vertex is slightly moved)

Code: Select all

$q=new Polytope<Rational>(VERTICES=>[[1,1,0],[1,2,15/10],[1,25/10,15/10],[1,3,0]],LINEALITY_SPACE=>[[]]); $qq=gc_closure($q); print $qq->VERTICES;
it returns following closure which should be identical to the previous one.

Code: Select all

1 1 0 1 2 1 1 5/2 1 1 3 0
Am I using something in incorrect way or is it a bug?

Thanks for info.
Peter

Edit: using polymake version 2.13

User avatar
assarf
Developer
Posts: 74
Joined: 12 Oct 2011, 15:52

Re: Function gc_closure

Postby assarf » 11 Feb 2015, 17:20

Hi there,

without investigating your examples in great detail, I think there is a misunderstanding here.

The function \(\texttt{gc_closure}\) does not compute the integer hull. It just does one iteration step. Doing the first gomory chvatal closure means: take all inequalities induced by the hilbert basis of the normal cones of each vertex and floor the right hand side (after you made sure the coefficients on the left side are integral).

If we repeat this process we will obtain the integer hull. Indeed if we call

Code: Select all

$q=new Polytope<Rational>(VERTICES=>[[1,1,0],[1,2,15/10],[1,25/10,15/10],[1,3,0]],LINEALITY_SPACE=>[[]]); $qq=gc_closure(gc_closure($q)); print $qq->VERTICES; 1 3 0 1 1 0 1 2 1
we get the same vertices as for your first example.

Since your second polytope has different inequalities and different normal cones I don't see why gc_closure should produce the same result. For me your output looks plausible.
no signature


Return to “Helpdesk”