Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revisionLast revisionBoth sides next revision | ||
tutorial:optimization [2013/08/23 16:01] – pfetsch | user_guide:tutorials:optimization [2019/01/25 10:56] – ↷ Links adapted because of a move operation 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 89: | Line 88: | ||
polytope > $p-> | polytope > $p-> | ||
</ | </ | ||
- | {{ :tutorial: | + | {{ user_guide: |
The minimal and maximal faces can be visualized via | The minimal and maximal faces can be visualized via | ||
Line 95: | Line 94: | ||
polytope > $p-> | polytope > $p-> | ||
</ | </ | ||
- | {{ :tutorial: | + | {{ user_guide: |
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 194: | Line 193: | ||
End | End | ||
</ | </ | ||
- | {{ :tutorial: | + | {{ user_guide: |
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 263: | Line 262: | ||
</ | </ | ||
- | {{ :tutorial: | + | {{ user_guide: |
Note that the upper right part (including the red vertices) arises from truncation of the polyhedron for visualization. | Note that the upper right part (including the red vertices) arises from truncation of the polyhedron for visualization. | ||
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); | ||
+ | |||
</ | </ | ||
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. | ||