user_guide:tutorials:latest:ilp_and_hilbertbases

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

user_guide:tutorials:latest:ilp_and_hilbertbases [2020/01/22 09:02] (current)
Line 1: Line 1:
 +===== 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>​
 +
  
  • user_guide/tutorials/latest/ilp_and_hilbertbases.txt
  • Last modified: 2020/01/22 09:02
  • (external edit)