user_guide:tutorials:ilp_and_hilbertbases

Differences

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

Link to this comparison view

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;​ +
-+
- +
-polytope > print $p->​SIMPLE;​ +
-+
-</​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);​ +
-+
-</​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;​ +
-+
- +
-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>​+
  
  • user_guide/tutorials/ilp_and_hilbertbases.txt
  • Last modified: 2019/02/04 22:55
  • (external edit)