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/07/29 18:23] – added files as paths oroehrig | ||
---|---|---|---|
Line 18: | Line 18: | ||
This tutorial is targeted towards the optimization community, since, surprisingly, | This tutorial is targeted towards the optimization community, since, surprisingly, | ||
+ | You can find files of the example LPs in the folder '' | ||
===== Input: lp2poly ===== | ===== Input: lp2poly ===== | ||
Line 35: | Line 36: | ||
</ | </ | ||
- | Thus, the file describes a 0/1-cube in three dimensions. It should be easy to adapt this format to other cases (If for example '' | + | Thus, the file describes a 0/1-cube in three dimensions. It should be easy to adapt this format to other cases (If for example '' |
- | + | ||
- | Now assume that this example is contained in file '' | + | |
< | < | ||
- | polytope > $f=lp2poly(' | + | polytope > $f=lp2poly(' |
</ | </ | ||
The polytope '' | The polytope '' | ||
Line 76: | Line 75: | ||
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 107: | ||
=== 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 134: | Line 133: | ||
We assume that the above information is contained in the file '' | We assume that the above information is contained in the file '' | ||
< | < | ||
- | polytope > $f=lp2poly(' | + | polytope > $f=lp2poly(' |
polytope > $p = new Polytope< | polytope > $p = new Polytope< | ||
</ | </ | ||
Line 198: | Line 197: | ||
We now assume that the example is contained in the file '' | We now assume that the example is contained in the file '' | ||
< | < | ||
- | polytope > $f = lp2poly(' | + | polytope > $f = lp2poly(' |
polytope > $pin = new Polytope< | polytope > $pin = new Polytope< | ||
</ | </ | ||
Line 292: | Line 291: | ||
In this example there are two integral variables '' | In this example there are two integral variables '' | ||
< | < | ||
- | polytope > $m=lp2poly(' | + | polytope > $m=lp2poly(' |
polytope > $p = new Polytope< | polytope > $p = new Polytope< | ||
</ | </ | ||
Line 335: | Line 334: | ||
In the second example, we reuse the file '' | In the second example, we reuse the file '' | ||
< | < | ||
- | polytope > $f=lp2poly(' | + | polytope > $f=lp2poly(' |
polytope > $p = new Polytope< | polytope > $p = new Polytope< | ||
</ | </ | ||
Line 354: | Line 353: | ||
* 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 379: | Line 378: | ||
Let us test whether the inequality system of this example is TDI. Thus, we first load the data as usual: | Let us test whether the inequality system of this example is TDI. Thus, we first load the data as usual: | ||
< | < | ||
- | polytope > $f = lp2poly(' | + | polytope > $f = lp2poly(' |
polytope > $p = new Polytope< | polytope > $p = new Polytope< | ||
</ | </ | ||
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 405: | ||
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 438: | Line 442: | ||
As before we read in the file using '' | As before we read in the file using '' | ||
< | < | ||
- | polytope > $f = lp2poly(' | + | polytope > $f = lp2poly(' |
polytope > $p = new Polytope< | polytope > $p = new Polytope< | ||
</ | </ | ||
- | 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 473: | ||
==== 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 521: | ||
===== 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. | ||