## ILP and Hilbert bases

### A first example

First we will construct a new rational polytope:

```polytope > \$p=new Polytope<Rational>;

polytope > \$p->POINTS=<<".";
polytope (2)> 1 0 0 0
polytope (3)> 1 1 0 0
polytope (4)> 1 0 1 0
polytope (5)> 1 1 1 0
polytope (6)> 1 0 0 1
polytope (7)> 1 1 0 1
polytope (8)> 1 0 1 1
polytope (9)> 1 1 1 1
polytope (10)> .```

Note that points in `polymake` are always given in homogenous coordinates. I.e., the point (a,b,c) in R3 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:

```polytope > print \$p->N_FACETS;
6

polytope > print \$p->SIMPLE;
1```

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`:

`polytope > \$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:

```polytope > print equal_polyhedra(\$p,\$c);
1```

### 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.

`polytope > \$rs = rand_sphere(3,20);`

`polymake` can of course visualise this polytope:

`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.

```polytope > \$lambda=2;

polytope > \$s=new Matrix<Rational>([[1,0,0,0],[0,\$lambda,0,0],[0,0,\$lambda,0],[0,0,0,\$lambda]]);

polytope > print \$s;
1 0 0 0
0 2 0 0
0 0 2 0
0 0 0 2

polytope > \$scaled_rs=new Polytope<Rational>(VERTICES=>(\$rs->VERTICES * \$s), LINEALITY_SPACE=>[]);```

`polymake` can visualise the polytope together with its lattice points:

`polytope > \$scaled_rs->VISUAL->LATTICE_COLORED;`

Now will construct the integer hull of `\$scaled_rs` and visualise it:

```polytope > \$integer_hull=new Polytope<Rational>(POINTS=>\$scaled_rs->LATTICE_POINTS);

polytope > \$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 [c0,c1, …, cd] corresponds to the linear objective c0 + c1x1 + … + cdxd.

`polytope > \$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.

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

And now we can perform some computations:

```polytope > print \$ilp->LP->MAXIMAL_VALUE;
2

polytope > print \$ilp->LP->MAXIMAL_FACE;
{6 9 10}

polytope > \$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.

```polytope > print \$ilp->VERTICES;
1 -1 0 -1
1 -1 0 1
1 -1 1 0
1 0 -1 -1
1 0 -1 1
1 0 1 -1
1 0 1 1
1 1 -1 0
1 1 0 -1
1 1 0 1
1 1 1 0```

### 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.

```polytope > print \$ilp->HILBERT_BASIS;
1 0 0 -1
1 -1 1 0
1 1 0 0
1 0 1 0
1 0 1 -1
1 1 1 0
1 0 1 1
1 1 0 -1
1 1 0 1
1 0 0 0
1 0 0 1
1 1 -1 0
1 -1 0 -1
1 -1 0 0
1 -1 0 1
1 0 -1 -1
1 0 -1 0
1 0 -1 1```
tutorial/ilp_and_hilbertbases.txt · Last modified: 2017/05/19 16:16 by oroehrig
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 4.0 International