integer hull

Questions and problems about using polymake go here.
stefan.erlangen

integer hull

Postby stefan.erlangen » 26 Jan 2011, 16:41

Hello,

I wanted to solve the following problem with polymake and could not find the solution in the tutorial.
I have a lp-file with about 20 (in-)equalities and 18 variables which I have read in with polymake with "lp2poly("myfile.lp");". now I can take a look at the inequalities as well as at the vertices and the facets (though there is a warning and I am not quite sure if that works correctly).

What I am a really looking for are the lattice points and the integer hull.

I hope somebody can help me with that little problem.

Stefan

herr
Developer
Posts: 40
Joined: 30 Dec 2010, 13:15

Re: integer hull

Postby herr » 26 Jan 2011, 19:58

lp2poly() returns a Polytope<Float>, which does not provide all the properties you need for your task. Therefore, you should convert it to a Polytope<Rational> via the user function convert_to<Rational>(), i.e.,

Code: Select all

$p=lp2poly("/my/file.lp"); $p_rat=convert_to<Rational>($p);
Now one way to compute the integer hull in polymake is to produce a new polytope from the lattice points of $p_rat:

Code: Select all

$lattice_points=$p_rat->LATTICE_POINTS; $p_lat=new Polytope<Rational>(POINTS=>$lattice_points);
The facets of $p_lat describe the integer hull.
Warning: The computation of the lattice points is quite expensive, so it might take some time, even for small examples.

paffenholz
Developer
Posts: 211
Joined: 24 Dec 2010, 13:47

Re: integer hull

Postby paffenholz » 26 Jan 2011, 23:39

There is also a script "gc_closure" that takes a rational polytope and returns its Chvatal-Gomory closure. Iterating this could be faster than computing all lattice points in the polytope. Scripts have to be loaded first:

Code: Select all

script("gc_closure");
If $p is your rational polytope, then

Code: Select all

$q=gc_closure($p)
computes the first elementary closure of $p.

Here is also a (somewhat incomplete) tutorial about solving ILP's with polymake. Computation of the integer hull is not yet included.

maudi
Posts: 7
Joined: 07 Feb 2011, 18:29

Re: integer hull

Postby maudi » 07 Feb 2011, 18:34

Hello,

is the script "gc_closure" available for download?

Thanks

paffenholz
Developer
Posts: 211
Joined: 24 Dec 2010, 13:47

Re: integer hull

Postby paffenholz » 08 Feb 2011, 17:39

is the script "gc_closure" available for download?
I am sorry, I was too quick with my answer.

The script is unfortunately not included in the current release 2.9.9 as it builds on things only available in the next release (computations with cones), so it won't help to make this available for download. If you want I can send you a workaround via mail. This would need an installed version of either 4ti2 or normaliz2 in addition to polymake.


Return to “Helpdesk”