# Differences

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

Both sides previous revision Previous revision Next revision | Previous revision | ||

user_guide:tutorials:ilp_and_hilbertbases [2019/01/25 09:35] oroehrig ↷ Links adapted because of a move operation |
user_guide:tutorials:ilp_and_hilbertbases [2019/02/04 22:55] (current) |
||
---|---|---|---|

Line 1: | Line 1: | ||

- | ===== ILP and Hilbert bases ===== | + | {{page>.:latest:@FILEID@}} |

- | | + | |

- | ==== A first example ==== | + | |

- | | + | |

- | First we will construct a new rational polytope: | + | |

- | <code> | + | |

- | 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)> . | + | |

- | </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> | + | |

- | polytope > print $p->N_FACETS; | + | |

- | 6 | + | |

- | | + | |

- | polytope > print $p->SIMPLE; | + | |

- | 1 | + | |

- | </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> | + | |

- | polytope > $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> | + | |

- | polytope > print equal_polyhedra($p,$c); | + | |

- | 1 | + | |

- | </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. | + | |

- | {{ user_guide:ilp:rand_sphere.png?200|}} | + | |

- | <code> | + | |

- | polytope > $rs = rand_sphere(3,20); | + | |

- | </code> | + | |

- | | + | |

- | ''polymake'' can of course visualise this polytope: | + | |

- | <code> | + | |

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

- | | + | |

- | {{ user_guide:ilp:rand_sphere_lattice.png?200|}} | + | |

- | <code> | + | |

- | 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=>[]); | + | |

- | </code> | + | |

- | | + | |

- | ''polymake'' can visualise the polytope together with its lattice points: | + | |

- | | + | |

- | <code> | + | |

- | polytope > $scaled_rs->VISUAL->LATTICE_COLORED; | + | |

- | </code> | + | |

- | | + | |

- | Now will construct the integer hull of ''$scaled_rs'' and visualise it: | + | |

- | | + | |

- | {{ user_guide:ilp:ilp_lattice.png?200|}} | + | |

- | <code> | + | |

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

- | | + | |

- | polytope > $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 [[user_guide:tutorials: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> | + | |

- | polytope > $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> | + | |

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

- | </code> | + | |

- | {{ user_guide:ilp:ilp_min_face.png?200|}} | + | |

- | {{ user_guide:ilp:ilp_max_face.png?200|}} | + | |

- | | + | |

- | And now we can perform some computations: | + | |

- | <code> | + | |

- | polytope > print $ilp->LP->MAXIMAL_VALUE; | + | |

- | 2 | + | |

- | | + | |

- | polytope > print $ilp->LP->MAXIMAL_FACE; | + | |

- | {6 9 10} | + | |

- | | + | |

- | polytope > $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> | + | |

- | 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 | + | |

- | </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> | + | |

- | 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 | + | |

- | </code> | + | |