user_guide:tutorials:latest:ilp_and_hilbertbases

# Differences

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

 — 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: + + + > $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<​sup>​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 [[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: + + + > 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. {{ :​tutorial:​ilp:​rand_sphere.png?​200|}} + + + >$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. + + {{ :​tutorial:​ilp:​rand//​sphere//​lattice.png?​200|}} + + + >$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: + + {{ :​tutorial:​ilp:​ilp_lattice.png?​200|}} + + + > $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 [[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,​c<​sub>​1,​ ..., c<​sub>​d​] corresponds to the linear objective c<​sub>​0​ + c<​sub>​1​x<​sub>​1​ + ... + c<​sub>​d​x<​sub>​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);​ + ​ + {{ :​tutorial:​ilp:​ilp//​max//​face.png?​200|}} + + 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 + ​ +
• user_guide/tutorials/latest/ilp_and_hilbertbases.txt