Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
user_guide:ilp_and_hilbertbases [2019/01/25 09:27] – ↷ Links adapted because of a move operation oroehrig | user_guide:tutorials:ilp_and_hilbertbases [2019/02/04 22:55] (current) – external edit 127.0.0.1 | ||
---|---|---|---|
Line 1: | Line 1: | ||
- | ===== ILP and Hilbert bases ===== | + | {{page>.:latest:@FILEID@}} |
- | + | ||
- | ==== 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, | + | |
- | </ | + | |
- | (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. | + | |
- | {{ user_guide: | + | |
- | <code> | + | |
- | 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. | + | |
- | + | ||
- | {{ user_guide:ilp:rand_sphere_lattice.png? | + | |
- | < | + | |
- | 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 '' | + | |
- | + | ||
- | {{ user_guide: | + | |
- | < | + | |
- | 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< | + | |
- | </ | + | |
- | {{ user_guide: | + | |
- | {{ user_guide: | + | |
- | + | ||
- | 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 | + | |
- | </ | + | |