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 15:52] – pfetschtutorial:optimization [2017/07/29 08:40] – [Input: lp2poly] saved file oroehrig
Line 37: Line 37:
 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 ''x1'' does not have any bounds you can write ''x1 free'' instead). 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 ''x1'' does not have any bounds you can write ''x1 free'' instead).
  
-Now assume that this example is contained in file ''c3t.lp''. We create a polytope from the file via:+Let us, for the sake of the example, save this in the file ''c3t.lp''. 
 +<code> 
 +> open(my $f, '> c3t.lp'); print $f "Minimize\n obj:  x1 + x2 + x3 
 +> Subject to\n C1: x1 + x2 + x3 <= 2 
 +> Bounds\n 0 <= x1 <= 1\n 0 <= x2 <= 1\n 0 <= x3 <= 1 
 +> End"; close $f; 
 +</code> 
 + 
 + 
 + 
 +We create a polytope from the file via:
 <code> <code>
 polytope > $f=lp2poly('c3t.lp'); polytope > $f=lp2poly('c3t.lp');
Line 76: Line 86:
 1 0 1 1 1 0 1 1
 </code> </code>
-This vertex corresponds to setting ''x1=0, x2=1, x3=3''. The optimal face can also be computed:+This vertex corresponds to setting ''x1=0, x2=1, x3=1''. The optimal face can also be computed:
 <code> <code>
 polytope > print $p->LP->MAXIMAL_FACE; polytope > print $p->LP->MAXIMAL_FACE;
Line 108: Line 118:
 === 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<sub>5</sub> with five nodes {1, 2, 3, 4, 5} and edges {1,2}, {2,3}, {3,4}, {4,5}, {5,1}. A formulation of the stable set problem for this graph looks as follows: For our example consider the 5-cycle, i.e., the graph C<sub>5</sub> with five nodes {1, 2, 3, 4, 5} and edges {1,2}, {2,3}, {3,4}, {4,5}, {5,1}. A formulation of the stable set problem for this graph looks as follows:
Line 414: Line 424:
 *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 457:
 </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 484:
 ==== 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 523: Line 532:
 ===== Lift-and-project closure ===== ===== 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: 
 +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 
 +</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: 
 +0: x2 >= 0 
 +1: x4 >= 0 
 +2: -x1 - x2 - x3 - x4 >= -1 
 +3: x3 >= 0 
 +4: 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. 
  
  
  
  
  • user_guide/tutorials/optimization.txt
  • Last modified: 2019/02/04 22:55
  • by 127.0.0.1