user_guide:tutorials:optimization

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision		 Previous revision
Next revisionBoth sides next revision
tutorial:optimization [2013/08/26 16:55] – added example for lift-and-project pfetschtutorial:optimization [2014/01/03 15:45] – external edit 127.0.0.1
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. *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 ===== ===== Chvátal-Gomory Closure =====
Line 448: Line 447:
 </code> </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> <code>
 polytope > $g = gc_closure($p); polytope > $g = gc_closure($p);
Line 475: 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://www.box.net/shared/at1y8i3pq434bxt6m9xm|Pokutta, 2011]]]. In our example, we use d = 4:
 <code> <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 > $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 529: Line 528:
    my $p = shift;    my $p = shift;
    my $d = $p->AMBIENT_DIM;    my $d = $p->AMBIENT_DIM;
-   my $q = new Polytope<Rational>(POINTS => ($p->VERTICES));+   my $q = new Polytope<Rational>($p);
    for (my $k = 0; $k < $d; $k = $k+1)    for (my $k = 0; $k < $d; $k = $k+1)
    {    {
Line 540: Line 539:
       my $v1 = new Vector<Rational>(0 | -unit_vector($d, $k));       my $v1 = new Vector<Rational>(0 | -unit_vector($d, $k));
       my $v2 = new Vector<Rational>(-1 | unit_vector($d, $k));       my $v2 = new Vector<Rational>(-1 | unit_vector($d, $k));
-      my $c1 = new Polytope<Rational>(INEQUALITIES => $v1); 
-      my $c2 = new Polytope<Rational>(INEQUALITIES => $v2); 
  
-      # intersect with input polytope +      # create intersection of corresponding polyhedra with iterated polyhedron $q 
-      my $b1 = intersection($c1, $p); +      my $b1 = new Polytope<Rational>(INEQUALITIES => $v1 / $q->FACETS); 
-      my $b2 = intersection($c2, $p);+      my $b2 = new Polytope<Rational>(INEQUALITIES => $v2 / $q->FACETS);
  
       if ( ($b1->DIM > -1) && ($b2->DIM > -1) )       if ( ($b1->DIM > -1) && ($b2->DIM > -1) )
Line 554: Line 551:
       elsif ( ($b1->DIM > -1) && ($b2->DIM == -1) )       elsif ( ($b1->DIM > -1) && ($b2->DIM == -1) )
       {       {
-  my $c = conv($b1); + $q = intersection($q, $b1);
-  $q = intersection($q, $c);+
       }       }
       elsif ( ($b1->DIM == -1) && ($b2->DIM > -1) )       elsif ( ($b1->DIM == -1) && ($b2->DIM > -1) )
       {       {
-  my $c = conv($b2); + $q = intersection($q, $b2);
-  $q = intersection($q, $c);+
       }       }
    }    }
Line 607: Line 602:
 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. 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.
  
-===== Other Software ===== 
  
  
  
  
  • user_guide/tutorials/optimization.txt
  • Last modified: 2019/02/04 22:55
  • by 127.0.0.1