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 [2014/05/27 08:10] – [Linear Optimization] paffenholz
Line 76: Line 76:
 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 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 603: 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