This tutorial is probably also available as a Jupyter notebook in the `demo`

folder in the polymake source and on github.

Different versions of this tutorial: latest release, release 4.0, release 3.6, release 3.5, release 3.4, nightly master

# ILP and Hilbert bases

## A first example

First we will construct a new rational polytope:

> $p=new Polytope<Rational>; > $p->POINTS=<<"."; > 1 0 0 0 > 1 1 0 0 > 1 0 1 0 > 1 1 1 0 > 1 0 0 1 > 1 1 0 1 > 1 0 1 1 > 1 1 1 1 > .

Note that points in `polymake`

are always given in homogenous coordinates. I.e., the point (a,b,c) in R^{3} is represented as `1 a b c`

in `polymake`

.

Now we can examine some properties of `$p`

. For instance we can determine the number of facets or whether `$p`

is simple:

> print $p->N_FACETS; 6 > print $p->SIMPLE; true

As you might already have noticed, our polytope is just a 3-dimensional cube. So there would have been an easier way to create it using the client `cube`

:

> $c = cube(3,0);

(You can check out the details of any function in the ''polymake'' documentation.)

And we can also verify that the two polytopes are actually equal:

> print equal_polyhedra($p,$c); true

## Another example

Now let us proceed with a somewhat more interesting example: The convex hull of 20 randomly chosen points on the 2-dimensional sphere.

> $rs = rand_sphere(3,20);

`polymake`

can of course visualise this polytope:

> $rs->VISUAL;

Now we will create yet another new polytope by scaling our random sphere by a factor lambda. (Otherwise there are rather few integral points contained in it.)

To this end, we have to multiply every coordinate (except for the homogenising 1 in the beginning) of every vertex by lamda. Then we can create a new polytope by specifying its vertices.

> $lambda=2; > $s=new Matrix<Rational>([[1,0,0,0],[0,$lambda,0,0],[0,0,$lambda,0],[0,0,0,$lambda]]); > print $s; 1 0 0 0 0 2 0 0 0 0 2 0 0 0 0 2 > $scaled_rs=new Polytope<Rational>(VERTICES=>($rs->VERTICES * $s), LINEALITY_SPACE=>[]);

`polymake`

can visualise the polytope together with its lattice points:

> $scaled_rs->VISUAL->LATTICE_COLORED;

Now will construct the integer hull of `$scaled_rs`

and visualise it:

> $integer_hull=new Polytope<Rational>(POINTS=>$scaled_rs->LATTICE_POINTS); > $integer_hull->VISUAL->LATTICE_COLORED;

In order to obtain the integer hull we simply define a new polytope `$integer_hull`

as the convex hull of all `LATTICE_POINTS`

contained in `$scaled_rs`

.

Note that if we give `POINTS`

(in contrast to `VERTICES`

) `polymake`

constructs a polytope that is the convex hull of the given points regardless of whether they are vertices or not. I.e., redundacies are allowed here.

If you specify `VERTICES`

you have to make sure yourself that your points are actually vertices since `polymake`

does not check this. You also need to specify the `LINEALITY_SPACE`

, see Tutorial on polytopes.

## Linear Programming

Now that we have constructed a nice integral polytope we want to apply some linear program to it.

First we define a `LinearProgram`

with our favourite `LINEAR_OBJECTIVE`

. The linear objective is an given as a vector of length d+1, d being the dimension of the space. The vector [c_{0},c_{1}, …, c_{d}] corresponds to the linear objective c_{0} + c_{1}x_{1} + … + c_{d}x_{d}.

> $objective=new LinearProgram<Rational>(LINEAR_OBJECTIVE=>[0,1,1,1]);

Then we define a new polytope, which is a copy of our old one (`$inter_hull`

) with the LP as an additional property.

> $ilp=new Polytope<Rational>(VERTICES=>$integer_hull->VERTICES, LP=>$objective);

And now we can perform some computations:

> print $ilp->LP->MAXIMAL_VALUE; 3 > print $ilp->LP->MAXIMAL_FACE; {11} > $ilp->VISUAL->MIN_MAX_FACE;

Hence the LP attains its maximal value 2 on the 2-face spanned by the vertices 6, 9 and 10.

`polymake`

can visualise the polytope and highlight both its maximal and minimal face in a different (by default admittedly almost painful ) colour. Here you see the maximal face `{6 9 10}`

in red and the minimal face `{0 3}`

(on the opposite side of the polytope) in yellow.

Note though that since we started out with a random polytope these results may vary if we perform the same computations another time on a different random polytope.

> print $ilp->VERTICES; 1 -1 -1 0 1 -1 0 -1 1 -1 0 1 1 -1 1 -1 1 -1 1 1 1 0 -1 -1 1 0 -1 1 1 0 1 -1 1 1 0 -1 1 1 0 1 1 1 1 0 1 1 1 1

## Hilbert bases

Finally, we can have `polymake`

compute and print a Hilbert basis for the cone spanned by `$ilp`

. Notice that this requires normaliz or 4ti2 to be installed in order to work.

> print $ilp->HILBERT_BASIS; 1 -1 -1 0 1 -1 0 -1 1 -1 0 0 1 -1 0 1 1 -1 1 -1 1 -1 1 0 1 -1 1 1 1 0 -1 -1 1 0 -1 0 1 0 -1 1 1 0 0 -1 1 0 0 0 1 0 0 1 1 0 1 -1 1 0 1 0 1 0 1 1 1 1 0 -1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1