===== ILP and Hilbert bases =====

==== A first example ====

First we will construct a new rational polytope:

<code perl>
> $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
> .
</code>
Note that points in ''polymake'' are always given in homogenous coordinates. I.e., the point (a,b,c) in R<sup>3</sup> 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:

<code perl>
> print $p->N_FACETS;
6
> print $p->SIMPLE;
true
</code>
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'':

<code perl>
> $c = cube(3,0);
</code>
(You can check out the details of any function in the [[http://wwwopt.mathematik.tu-darmstadt.de/polymake_doku/2.9.8/|''polymake'' documentation]].)

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

<code perl>
> print equal_polyhedra($p,$c);
true
</code>
==== 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. {{ :tutorial:ilp:rand_sphere.png?200|}}

<code perl>
> $rs = rand_sphere(3,20);
</code>
''polymake'' can of course visualise this polytope:

<code perl>
> $rs->VISUAL;
</code>
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.

{{ :tutorial:ilp:rand//sphere//lattice.png?200|}}

<code perl>
> $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=>[]);
</code>
''polymake'' can visualise the polytope together with its lattice points:

<code perl>
> $scaled_rs->VISUAL->LATTICE_COLORED;
</code>
Now will construct the integer hull of ''$scaled_rs'' and visualise it:

{{ :tutorial:ilp:ilp_lattice.png?200|}}

<code perl>
> $integer_hull=new Polytope<Rational>(POINTS=>$scaled_rs->LATTICE_POINTS);
> $integer_hull->VISUAL->LATTICE_COLORED;
</code>
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 [[apps_polytope|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<sub>0</sub>,c<sub>1</sub>, ..., c<sub>d</sub>] corresponds to the linear objective c<sub>0</sub> + c<sub>1</sub>x<sub>1</sub> + ... + c<sub>d</sub>x<sub>d</sub>.

<code perl>
> $objective=new LinearProgram<Rational>(LINEAR_OBJECTIVE=>[0,1,1,1]);
</code>
Then we define a new polytope, which is a copy of our old one (''$inter_hull'') with the LP as an additional property.

<code perl>
> $ilp=new Polytope<Rational>(VERTICES=>$integer_hull->VERTICES, LP=>$objective);
</code>
{{ :tutorial:ilp:ilp//max//face.png?200|}}

And now we can perform some computations:

<code perl>
> print $ilp->LP->MAXIMAL_VALUE;
3
> print $ilp->LP->MAXIMAL_FACE;
{11}
> $ilp->VISUAL->MIN_MAX_FACE;
</code>
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.

<code perl>
> 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
</code>
==== 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.

<code perl>
> 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
</code>