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.13, release 4.12, release 4.11, release 4.10, release 4.9, release 4.8, release 4.7, release 4.6, release 4.5, release 4.4, release 4.3, release 4.2, release 4.1, release 4.0, release 3.6, 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 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;

**Transparency**

**Rotation**

**Display**

**Camera**

**SVG**

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;

**Explode**

**Transparency**

**Rotation**

**Display**

**Camera**

**SVG**

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;

**Explode**

**Transparency**

**Rotation**

**Display**

**Camera**

**SVG**

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;

**Transparency**

**Rotation**

**Display**

**Camera**

**SVG**

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 -1 1 -1 -1 0 1 -1 0 1 1 -1 1 0 1 -1 1 1 1 0 -1 0 1 0 -1 1 1 0 1 -1 1 1 0 0 1 1 0 1 1 1 1 -1 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 -1 1 -1 -1 0 1 -1 0 0 1 -1 0 1 1 -1 1 0 1 -1 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 0 1 1 0 1 1 1 1 -1 1 1 1 0 1 1 1 1