Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revisionBoth sides next revision | ||
tutorial:optimization [2013/08/23 16:01] – pfetsch | tutorial:optimization [2014/05/27 08:10] – [Linear Optimization] paffenholz | ||
---|---|---|---|
Line 76: | Line 76: | ||
1 0 1 1 | 1 0 1 1 | ||
</ | </ | ||
- | This vertex corresponds to setting '' | + | This vertex corresponds to setting '' |
< | < | ||
polytope > print $p-> | polytope > print $p-> | ||
Line 314: | Line 314: | ||
As explained in the previous example, the integral points in a polytope are of particular interest in discrete optimization. These points are called //lattice points// in polymake and the corresponding convex hull //lattice polytope//. The handling of such polytopes is explained in more detail in the [[tutorial: | As explained in the previous example, the integral points in a polytope are of particular interest in discrete optimization. These points are called //lattice points// in polymake and the corresponding convex hull //lattice polytope//. The handling of such polytopes is explained in more detail in the [[tutorial: | ||
- | Of particular interest for discrete optimization are properties of the orginal inequality system to define a lattice polytope, i.e., a polytope such that all of its vertices are integral. One particularly interesting case occurs if the matrix defining the polytope is //totally unimodular// | + | Of particular interest for discrete optimization are properties of the orginal inequality system to define a lattice polytope, i.e., a polytope such that all of its vertices are integral |
Using the polymake extension [[https:// | Using the polymake extension [[https:// | ||
Line 354: | Line 354: | ||
* The function '' | * The function '' | ||
- | Note that the input has to be full-dimensional in order to use these functions | + | Note that the input has to be full-dimensional in order to use these functions. |
To demonstrate the behavior of these functions, consider the 5-cycle example from above again: | To demonstrate the behavior of these functions, consider the 5-cycle example from above again: | ||
Line 384: | Line 384: | ||
We now extract the corresponding inequality system and check it for TDIness: | We now extract the corresponding inequality system and check it for TDIness: | ||
< | < | ||
- | polytope> | + | polytope > $M = new Matrix< |
polytope > totally_dual_integral($M); | polytope > totally_dual_integral($M); | ||
+ | |||
</ | </ | ||
Since the last line is empty, the system is not TDI, which we expected from general theory, since we know that the polytope is not integral, but the system has integral coefficients. Consequently, | Since the last line is empty, the system is not TDI, which we expected from general theory, since we know that the polytope is not integral, but the system has integral coefficients. Consequently, | ||
Line 406: | Line 406: | ||
11: 0 >= -1 | 11: 0 >= -1 | ||
</ | </ | ||
- | As expected, the right hand side is non integral (otherwise, we know from general theory that the polytope would be integral as well). | + | As expected, the right hand side is non integral (otherwise, we know from general theory that the polytope would be integral as well). The result is now TDI: |
+ | < | ||
+ | polytope > $N = new Matrix< | ||
+ | polytope > print totally_dual_integral($N); | ||
+ | 1 | ||
+ | </ | ||
+ | *Note* that we need to take the inequalities instead of facets here, since facets are irredundant and thus might not be TDI, although the complete set of inequalities is TDI. | ||
- | ===== 0/ | ||
===== Chvátal-Gomory Closure ===== | ===== Chvátal-Gomory Closure ===== | ||
Line 442: | Line 447: | ||
</ | </ | ||
- | The Chvátal-Gomory closure of a polytope can be computed with the function '' | + | The Chvátal-Gomory closure of a polytope can be computed with the function '' |
< | < | ||
polytope > $g = gc_closure($p); | polytope > $g = gc_closure($p); | ||
Line 469: | Line 474: | ||
==== Chvátal-Gomory Closure - Example 2 ==== | ==== Chvátal-Gomory Closure - Example 2 ==== | ||
- | Let us now consider the classical example of a polytope with the vertices of simplex in d dimensions and the point 1/2 times (1, ..., 1). It can be shown that such a polytope has rank at least log(d) - 1, see [Pokutta, 2011]. In our example, we use d = 4: | + | Let us now consider the classical example of a polytope with the vertices of simplex in d dimensions and the point 1/2 times (1, ..., 1). It can be shown that such a polytope has rank at least log(d) - 1, see [[http:// |
< | < | ||
polytope > $M = new Matrix< | polytope > $M = new Matrix< | ||
Line 517: | Line 522: | ||
===== Lift-and-project closure ===== | ===== Lift-and-project closure ===== | ||
- | ===== Other Software | + | The lift-and-project closure of a 0/ |
+ | < | ||
+ | sub lpclosure | ||
+ | { | ||
+ | my $p = shift; | ||
+ | my $d = $p-> | ||
+ | my $q = new Polytope< | ||
+ | for (my $k = 0; $k < $d; $k = $k+1) | ||
+ | { | ||
+ | if ( $q-> | ||
+ | { | ||
+ | return $q; | ||
+ | } | ||
+ | |||
+ | # create reversed opposite inequalities of 0/1-cube and corresponding polyhedra | ||
+ | my $v1 = new Vector< | ||
+ | my $v2 = new Vector< | ||
+ | |||
+ | # create intersection of corresponding polyhedra with iterated polyhedron $q | ||
+ | my $b1 = new Polytope< | ||
+ | my $b2 = new Polytope< | ||
+ | |||
+ | if ( ($b1-> | ||
+ | { | ||
+ | my $c = conv($b1, $b2); | ||
+ | $q = intersection($q, | ||
+ | } | ||
+ | elsif ( ($b1-> | ||
+ | { | ||
+ | $q = intersection($q, | ||
+ | } | ||
+ | elsif ( ($b1-> | ||
+ | { | ||
+ | $q = intersection($q, | ||
+ | } | ||
+ | } | ||
+ | | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ==== Lift-and-Projet Closure - Example 1 ==== | ||
+ | |||
+ | For our well known stable set example, we get the following: | ||
+ | < | ||
+ | polytope > $q = lpclosure($p); | ||
+ | polytope > $q-> | ||
+ | polytope > print_constraints($q); | ||
+ | Facets: | ||
+ | 0: -x4 - x5 >= -1 | ||
+ | 1: -x2 - x3 >= -1 | ||
+ | 2: -x1 - x2 - x3 - x4 - x5 >= -2 | ||
+ | 3: -x1 - x5 >= -1 | ||
+ | 4: -x3 - x4 >= -1 | ||
+ | 5: x2 >= 0 | ||
+ | 6: x1 >= 0 | ||
+ | 7: x3 >= 0 | ||
+ | 8: -x1 - x2 >= -1 | ||
+ | 9: x4 >= 0 | ||
+ | 10: x5 >= 0 | ||
+ | </ | ||
+ | Thus, the lift-and-project closure in this case gives the integral hull (as we have seen above). | ||
+ | |||
+ | ==== Lift-and-Projet Closure - Example 2 ==== | ||
+ | |||
+ | Let us now consider the same example as for CG-closures: | ||
+ | < | ||
+ | polytope > $M = new Matrix< | ||
+ | polytope > $p = new Polytope< | ||
+ | polytope > $q = lpclosure($p); | ||
+ | polytope > $q-> | ||
+ | polytope > print_constraints($q); | ||
+ | Facets: | ||
+ | 0: x2 >= 0 | ||
+ | 1: x4 >= 0 | ||
+ | 2: -x1 - x2 - x3 - x4 >= -1 | ||
+ | 3: x3 >= 0 | ||
+ | 4: x1 >= 0 | ||
+ | </ | ||
+ | Thus, we have obtained the integral hull in a single step of the lift-and-project closure as opposed to two steps in the CG-closure. | ||