Differences

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

--- tutorial:ilp_tutorial [2010/05/04 13:52] – created silke
+++ tutorial:ilp_tutorial [2017/07/31 17:31] – removed empty tutorial link oroehrig
@@ Line 1: / Line 1: @@
 ===== Integer Linear Programming =====
-This tutorial shall give an introduction to ILP in ''polymake''. It is primarily aimed at students of the course "Discrete Optimization" at TU Darmstadt and based on a demo shown in the lecture.
+These tutorials shall give an introduction to ILP in ''polymake''. They are primarily aimed at students of the course "Discrete Optimization" at TU Darmstadt and based on demos shown in the lecture.
+  *[[ilp_and_hilbertbases|ILP and Hilbert bases]]
+  *[[matching_polytopes|Matching polytopes]]
+  *[[caratheodory|A Counter-example to an integer analogue to Caratheodory's Theorem]]
-==== 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.
-{{ :tutorial: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.
-{{ :tutorial: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;
-0 0 0
-2 0 0
-0 2 0
-0 0 2
-polytope > $scaled_rs=new Polytope<Rational>(VERTICES=>($rs->VERTICES * $s));
-</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:
-{{ :tutorial: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.
-==== 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>
-{{ :tutorial:ilp:ilp_min_face.png?200|}}
-{{ :tutorial: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 0 -1
--1 0 1
--1 1 0
-0 -1 -1
-0 -1 1
-0 1 -1
-0 1 1
-1 -1 0
-1 0 -1
-1 0 1
-1 1 0
-</code>
-==== Hilbert bases ====
-Finally, we can have ''polymake'' compute and print a Hilbert basis for the cone spanned by ''$ilp''.
-<code>
-polytope > print $ilp->HILBERT_BASIS;
-0 0 -1
--1 1 0
-1 0 0
-0 1 0
-0 1 -1
-1 1 0
-0 1 1
-1 0 -1
-1 0 1
-0 0 0
-0 0 1
-1 -1 0
--1 0 -1
--1 0 0
--1 0 1
-0 -1 -1
-0 -1 0
-0 -1 1
-</code>
+The following tutorials were written by Michael Schmitt, a student of the course:
+  *[[michaels_tutorial|Michael's Tutorial on Branch & Bound]]
+  *[[michaels_tutorial2|Michael's Tutorial on Gomory Cuts]]