user_guide:tutorials:ilp_and_hilbertbases

# Differences

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

 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) 2019/01/25 09:38 oroehrig ↷ Page moved from user_guide:ilp_and_hilbertbases to user_guide:tutorials:ilp_and_hilbertbases2019/01/25 09:35 oroehrig ↷ Links adapted because of a move operation2019/01/25 09:27 oroehrig ↷ Links adapted because of a move operation2019/01/25 09:27 oroehrig ↷ Page moved from tutorial:ilp_and_hilbertbases to user_guide:ilp_and_hilbertbases2017/05/19 16:16 oroehrig fixed wrong declaration of empty lineality2014/01/03 15:45 external edit2012/05/16 12:32 herr added comment on lineality space2010/06/07 07:35 silke 2010/06/07 07:34 silke created 2019/01/25 09:38 oroehrig ↷ Page moved from user_guide:ilp_and_hilbertbases to user_guide:tutorials:ilp_and_hilbertbases2019/01/25 09:35 oroehrig ↷ Links adapted because of a move operation2019/01/25 09:27 oroehrig ↷ Links adapted because of a move operation2019/01/25 09:27 oroehrig ↷ Page moved from tutorial:ilp_and_hilbertbases to user_guide:ilp_and_hilbertbases2017/05/19 16:16 oroehrig fixed wrong declaration of empty lineality2014/01/03 15:45 external edit2012/05/16 12:32 herr added comment on lineality space2010/06/07 07:35 silke 2010/06/07 07:34 silke created 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)> . + - ​ + - 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: + - <​code>​ + - 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'':​ + - <​code>​ + - polytope > $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: + - <​code>​ + - 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. + - {{ user_guide:​ilp:​rand_sphere.png?​200|}} + - + - polytope >$rs = rand_sphere(3,​20);​ + - ​ + - + - ''​polymake''​ can of course visualise this polytope: + - <​code>​ + - 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. + - + - {{ 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=>​[]);​ + - ​ + - + - ''​polymake''​ can visualise the polytope together with its lattice points: + - + - <​code>​ + - polytope > $scaled_rs->​VISUAL->​LATTICE_COLORED;​ + - ​ + - + - 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;​ + - ​ + - 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,​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​. + - <​code>​ + - 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. + - <​code>​ + - polytope >$ilp=new Polytope<​Rational>​(VERTICES=>​$integer_hull->​VERTICES,​ LP=>​$objective);​ + - ​ + - {{ 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;​ + - ​ + - 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 + - ​ + - + - ==== 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 + - ​ +
• user_guide/tutorials/ilp_and_hilbertbases.txt