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/09 18:48] – removed superfluous sections, fixed typo 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:
  • user_guide/tutorials/optimization.txt
  • Last modified: 2019/02/04 22:55
  • by 127.0.0.1