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/22 19:56] – [Chvátal-Gomory Closure - Example 1] pfetsch | user_guide:optimization [2019/01/25 09:27] – ↷ Page moved from tutorial:optimization to user_guide:optimization oroehrig | ||
---|---|---|---|
Line 11: | Line 11: | ||
There are several other tutorials that cover similar topics: | There are several other tutorials that cover similar topics: | ||
- | * [[tutorial: | + | * [[user_guide: |
- | * [[tutorial: | + | * [[user_guide: |
- | * [[tutorial: | + | * [[user_guide: |
- | * [[tutorial: | + | * [[user_guide: |
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 312: | Line 311: | ||
===== Integral Polytopes and Total Unimodularity ===== | ===== Integral Polytopes and Total Unimodularity ===== | ||
- | 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 [[user_guide: |
- | 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 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); | ||
- | 0 | + | |
</ | </ | ||
- | Hence, the system is not TDI, which we expected from general theory, since we know that the polytope is not integral, but the system | + | 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 |
< | < | ||
polytope > $q = make_totally_dual_integral($p); | polytope > $q = make_totally_dual_integral($p); | ||
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 460: | Line 464: | ||
11: 0 >= -1 | 11: 0 >= -1 | ||
</ | </ | ||
- | Let us check whether the resulting polytope is integral | + | Let us check whether the resulting polytope is integral: |
< | < | ||
- | polytope > print $g->VERTICES; | + | polytope > print $g->LATTICE; |
- | 1 0 0 0 1 0 | + | 1 |
- | 1 0 0 0 0 1 | + | |
- | 1 0 1 0 0 0 | + | |
- | 1 0 0 0 0 0 | + | |
- | 1 1 0 0 0 0 | + | |
- | 1 0 0 1 0 0 | + | |
- | 1 1 0 1 0 0 | + | |
- | 1 0 1 0 0 1 | + | |
- | 1 1 0 0 1 0 | + | |
- | 1 0 1 0 1 0 | + | |
- | 1 0 0 1 0 1 | + | |
</ | </ | ||
Thus, in this case, we have obtained the integer hull by one step of the Chvatal-Gomory-closure. | Thus, in this case, we have obtained the integer hull by one step of the Chvatal-Gomory-closure. | ||
Line 479: | 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 495: | Line 489: | ||
6: -x1 - x3 - x4 >= -1 | 6: -x1 - x3 - x4 >= -1 | ||
7: -x2 - x3 - x4 >= -1 | 7: -x2 - x3 - x4 >= -1 | ||
+ | polytope > print $t1-> | ||
+ | 0 | ||
+ | </ | ||
+ | Thus, one round was not enough to produce an integral polytope. Indeed, the vertices are | ||
+ | < | ||
polytope > $t1-> | polytope > $t1-> | ||
polytope > print $t1-> | polytope > print $t1-> | ||
Line 504: | Line 503: | ||
1 0 0 0 1 | 1 0 0 0 1 | ||
</ | </ | ||
- | Thus, one round was not enough to produce an integral polytope. | + | |
+ | However, one more round is enough: | ||
< | < | ||
polytope > $t2 = gc_closure($t1); | polytope > $t2 = gc_closure($t1); | ||
Line 515: | Line 515: | ||
3: x1 >= 0 | 3: x1 >= 0 | ||
4: -x1 - x2 - x3 - x4 >= -1 | 4: -x1 - x2 - x3 - x4 >= -1 | ||
+ | polytope > print $t2-> | ||
+ | 1 | ||
</ | </ | ||
===== 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. | ||