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:03] – [Integral Polytopes and Total Unimodularity] pfetsch | tutorial:optimization [2017/03/23 14:23] – [Pure Integer Case] cfischer | ||
---|---|---|---|
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 108: | Line 108: | ||
=== Bounded Polyhedra === | === Bounded Polyhedra === | ||
- | Let us illustrate the approach via the example of the //stable set problem//: Here one is given an (undirected) Graph G = (V,E) with node set V and edges E. The goal is to find a largest subset of node V' such that any two nodes in V' are not connected by an edge. | + | Let us illustrate the approach via the example of the //stable set problem//: Here one is given an (undirected) Graph G = (V,E) with node set V and edges E. The goal is to find a largest subset of nodes V' such that any two nodes in V' are not connected by an edge. |
For our example consider the 5-cycle, i.e., the graph C< | For our example consider the 5-cycle, i.e., the graph C< | ||
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. | ||