Differences
This shows you the differences between two versions of the page.
Next revision | Previous revision | ||
tutorial:ilp_tutorial [2010/05/04 13:52] – created silke | tutorial:ilp_tutorial [2017/07/31 18:07] (current) – migrated overview to tutorial overview page oroehrig | ||
---|---|---|---|
Line 1: | Line 1: | ||
- | ===== Integer Linear Programming ===== | ||
- | |||
- | This tutorial shall give an introduction to ILP in '' | ||
- | |||
- | |||
- | ==== A first example ==== | ||
- | |||
- | First we will construct a new rational polytope: | ||
- | < | ||
- | polytope > $p=new Polytope< | ||
- | |||
- | polytope > $p-> | ||
- | 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 '' | ||
- | |||
- | Now we can examine some properties of '' | ||
- | < | ||
- | polytope > print $p-> | ||
- | 6 | ||
- | |||
- | polytope > print $p-> | ||
- | 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 '' | ||
- | < | ||
- | polytope > $c = cube(3,0); | ||
- | </ | ||
- | (You can check out the details of any function in the [[http:// | ||
- | |||
- | And we can also verify that the two polytopes are actually equal: | ||
- | < | ||
- | polytope > print equal_polyhedra($p, | ||
- | 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. | ||
- | {{ : | ||
- | < | ||
- | polytope > $rs = rand_sphere(3, | ||
- | </ | ||
- | |||
- | '' | ||
- | < | ||
- | polytope > $rs-> | ||
- | </ | ||
- | |||
- | 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. | ||
- | |||
- | {{ : | ||
- | < | ||
- | polytope > $lambda=2; | ||
- | |||
- | polytope > $s=new Matrix< | ||
- | |||
- | polytope > print $s; | ||
- | 1 0 0 0 | ||
- | 0 2 0 0 | ||
- | 0 0 2 0 | ||
- | 0 0 0 2 | ||
- | |||
- | polytope > $scaled_rs=new Polytope< | ||
- | </ | ||
- | |||
- | '' | ||
- | |||
- | < | ||
- | polytope > $scaled_rs-> | ||
- | </ | ||
- | |||
- | Now will construct the integer hull of '' | ||
- | |||
- | {{ : | ||
- | < | ||
- | polytope > $integer_hull=new Polytope< | ||
- | |||
- | polytope > $integer_hull-> | ||
- | </ | ||
- | In order to obtain the integer hull we simply define a new polytope '' | ||
- | |||
- | Note that if we give '' | ||
- | |||
- | If you specify '' | ||
- | |||
- | ==== Linear Programming ==== | ||
- | |||
- | Now that we have constructed a nice integral polytope we want to apply some linear program to it. | ||
- | |||
- | First we define a '' | ||
- | < | ||
- | polytope > $objective=new LinearProgram< | ||
- | </ | ||
- | Then we define a new polytope, which is a copy of our old one ('' | ||
- | < | ||
- | polytope > $ilp=new Polytope< | ||
- | </ | ||
- | {{ : | ||
- | {{ : | ||
- | |||
- | And now we can perform some computations: | ||
- | < | ||
- | polytope > print $ilp-> | ||
- | 2 | ||
- | |||
- | polytope > print $ilp-> | ||
- | {6 9 10} | ||
- | |||
- | polytope > $ilp-> | ||
- | </ | ||
- | Hence the LP attains its maximal value 2 on the 2-face spanned by the vertices 6, 9 and 10. | ||
- | |||
- | '' | ||
- | |||
- | |||
- | 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. | ||
- | |||
- | < | ||
- | polytope > print $ilp-> | ||
- | 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 '' | ||
- | < | ||
- | polytope > print $ilp-> | ||
- | 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 | ||
- | </ | ||