Differences

This shows you the differences between two versions of the page.

--- tutorial:optimization [2013/08/26 15:52] – pfetsch
+++ tutorial:optimization [2013/09/09 18:48] – removed superfluous sections, fixed typo pfetsch
@@ Line 414: / Line 414: @@
 *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/1-Polytopes =====
 ===== Chvátal-Gomory Closure =====
@@ Line 448: / Line 447: @@
 </code>
-The Chvátal-Gomory closure of a polytope can be computed with the function ''gc_closure''. The function takes a full-dimensional polytope and returns a new polytope. This contains the system of inequlities defining the closure in the property ''INEQUALITIES''. For our example, we obtain:
+The Chvátal-Gomory closure of a polytope can be computed with the function ''gc_closure''. The function takes a full-dimensional polytope and returns a new polytope. This contains the system of inequalities defining the closure in the property ''INEQUALITIES''. For our example, we obtain:
 <code>
 polytope > $g = gc_closure($p);
@@ Line 475: / Line 474: @@
 ==== 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://www.box.net/shared/at1y8i3pq434bxt6m9xm|Pokutta, 2011]]]. In our example, we use d = 4:
 <code>
 polytope > $M = new Matrix<Rational>([[1,0,0,0,0],[1,1,0,0,0],[1,0,1,0,0],[1,0,0,1,0],[1,0,0,0,1],[1,1/2,1/2,1/2,1/2]]);
@@ Line 523: / Line 522: @@
 ===== Lift-and-project closure =====
-===== Other Software =====
+The lift-and-project closure of a 0/1-polytope P can be generated as follows: for each coordinate compute the intersection of P with the pair of opposite cube faces and compute the convex hull. Then intersect the result with P. The following subroutine performs this operation - the code is somewhat complicated throught the fact that we need to check whether parts are empty.
+<code>
+sub lpclosure
+{
+   my $p = shift;
+   my $d = $p->AMBIENT_DIM;
+   my $q = new Polytope<Rational>($p);
+   for (my $k = 0; $k < $d; $k = $k+1)
+   {
+      if ( $q->DIM == -1 )         # can stop as soon as $q is empty
+      {
+	 return $q;
+      }
+      # create reversed opposite inequalities of 0/1-cube and corresponding polyhedra
+      my $v1 = new Vector<Rational>(0 | -unit_vector($d, $k));
+      my $v2 = new Vector<Rational>(-1 | unit_vector($d, $k));
+      # create intersection of corresponding polyhedra with iterated polyhedron $q
+      my $b1 = new Polytope<Rational>(INEQUALITIES => $v1 / $q->FACETS);
+      my $b2 = new Polytope<Rational>(INEQUALITIES => $v2 / $q->FACETS);
+      if ( ($b1->DIM > -1) && ($b2->DIM > -1) )
+      {
+	 my $c = conv($b1, $b2);
+	 $q = intersection($q, $c);
+      }
+      elsif ( ($b1->DIM > -1) && ($b2->DIM == -1) )
+      {
+	 $q = intersection($q, $b1);
+      }
+      elsif ( ($b1->DIM == -1) && ($b2->DIM > -1) )
+      {
+	 $q = intersection($q, $b2);
+      }
+   }
+   return $q;
+}
+</code>
+==== Lift-and-Projet Closure - Example 1 ====
+For our well known stable set example, we get the following:
+<code>
+polytope > $q = lpclosure($p);
+polytope > $q->FACETS;
+polytope > print_constraints($q);
+Facets:
+: -x4 - x5 >= -1
+: -x2 - x3 >= -1
+: -x1 - x2 - x3 - x4 - x5 >= -2
+: -x1 - x5 >= -1
+: -x3 - x4 >= -1
+: x2 >= 0
+: x1 >= 0
+: x3 >= 0
+: -x1 - x2 >= -1
+: x4 >= 0
+: x5 >= 0
+</code>
+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:
+<code>
+polytope > $M = new Matrix<Rational>([[1,0,0,0,0],[1,1,0,0,0],[1,0,1,0,0],[1,0,0,1,0],[1,0,0,0,1],[1,1/2,1/2,1/2,1/2]]);
+polytope > $p = new Polytope<Rational>(POINTS => $M);
+polytope > $q = lpclosure($p);
+polytope > $q->FACETS;
+polytope > print_constraints($q);
+Facets:
+: x2 >= 0
+: x4 >= 0
+: -x1 - x2 - x3 - x4 >= -1
+: x3 >= 0
+: x1 >= 0
+</code>
+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.