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/09/04 15:01] – fixed L&P-code 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 603: Line 612:
 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