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
Last revisionBoth sides next revision
tutorial:optimization [2017/07/29 08:40] – [Input: lp2poly] saved file oroehriguser_guide:tutorials:optimization [2019/01/25 10:56] – ↷ Links adapted because of a move operation oroehrig
Line 11: Line 11:
  
 There are several other tutorials that cover similar topics: There are several other tutorials that cover similar topics:
-  * [[tutorial:ilp_and_hilbertbases|ILP and Hilbert Bases]] +  * [[user_guide:tutorials:ilp_and_hilbertbases|ILP and Hilbert Bases]] 
-  * [[tutorial:michaels_tutorial2|Gomory Cuts]] +  * [[user_guide:tutorials:michaels_tutorial2|Gomory Cuts]] 
-  * [[tutorial:michaels_tutorial|Branch and Bound]] +  * [[user_guide:tutorials:michaels_tutorial|Branch and Bound]] 
-  * [[tutorial:lattice_polytopes_tutorial|Tutorial for Lattice Polytopes]]+  * [[user_guide:tutorials:lattice_polytopes_tutorial|Tutorial for Lattice Polytopes]]
  
 This tutorial is targeted towards the optimization community, since, surprisingly, polymake does not seem to be well known in this community. In particular, the community still tends to use the quite old program ''porta'' to compute convex hulls or inequality descriptions. While ''porta'' still does a decent job here, ''polymake'' offers a much broader feature set. Polymake supports several convex hull algorithms which might be better suited depending on the data. Moreover it offers many visualization tools that can help to better //understand// a given polytope. We think that polymake has many advantages for discrete optimizers and hope that this tutorial will help to spread the usage of polymake. This tutorial is targeted towards the optimization community, since, surprisingly, polymake does not seem to be well known in this community. In particular, the community still tends to use the quite old program ''porta'' to compute convex hulls or inequality descriptions. While ''porta'' still does a decent job here, ''polymake'' offers a much broader feature set. Polymake supports several convex hull algorithms which might be better suited depending on the data. Moreover it offers many visualization tools that can help to better //understand// a given polytope. We think that polymake has many advantages for discrete optimizers and hope that this tutorial will help to spread the usage of polymake.
  
 +You can find files of the example LPs in the folder ''demo/optimization_tut'' in your ''polymake'' directory.
  
 ===== Input: lp2poly ===== ===== Input: lp2poly =====
Line 35: Line 36:
 </code> </code>
  
-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). 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('demo/optimization_tut/c3t.lp');
 </code> </code>
 The polytope ''$f'' is coded via floating point numbers: The polytope ''$f'' is coded via floating point numbers:
Line 99: Line 88:
 polytope > $p->VISUAL->DIRECTED_GRAPH; polytope > $p->VISUAL->DIRECTED_GRAPH;
 </code> </code>
-{{ :tutorial:c3t_graph.gif?300 }}+{{ user_guide:c3t_graph.gif?300 }}
  
 The minimal and maximal faces can be visualized via The minimal and maximal faces can be visualized via
Line 105: Line 94:
 polytope > $p->VISUAL->MIN_MAX_FACE; polytope > $p->VISUAL->MIN_MAX_FACE;
 </code> </code>
-{{ :tutorial:c3t_maxface.gif?300 |}}+{{ user_guide:c3t_maxface.gif?300 |}}
  
  
Line 144: Line 133:
 We assume that the above information is contained in the file ''stab.lp''. We now read it into polymake and convert it to rational form, as explained above: We assume that the above information is contained in the file ''stab.lp''. We now read it into polymake and convert it to rational form, as explained above:
 <code> <code>
-polytope > $f=lp2poly('stab.lp');+polytope > $f=lp2poly('demo/optimization_tut/stab.lp');
 polytope > $p = new Polytope<Rational>($f); polytope > $p = new Polytope<Rational>($f);
 </code> </code>
Line 204: Line 193:
 End End
 </code> </code>
-{{ :tutorial:ip-unb.gif?300 | Picture of unbounded polyhedron (truncated at upper right)}}+{{ user_guide:ip-unb.gif?300 | Picture of unbounded polyhedron (truncated at upper right)}}
  
 We now assume that the example is contained in the file ''unbounded.lp'' and proceed as above We now assume that the example is contained in the file ''unbounded.lp'' and proceed as above
 <code> <code>
-polytope > $f = lp2poly('unbounded.lp');+polytope > $f = lp2poly('demo/optimization_tut/unbounded.lp');
 polytope > $pin = new Polytope<Rational>($f); polytope > $pin = new Polytope<Rational>($f);
 </code> </code>
Line 273: Line 262:
 </code> </code>
  
-{{ :tutorial:ip-unb-integerhull.gif?300 |}}+{{ user_guide:ip-unb-integerhull.gif?300 |}}
  
 Note that the upper right part (including the red vertices) arises from truncation of the polyhedron for visualization. Note that the upper right part (including the red vertices) arises from truncation of the polyhedron for visualization.
Line 302: Line 291:
 In this example there are two integral variables ''x1'' and ''x2'', while ''s1'' and ''s2'' are continuous variables. Assuming the data is contained in the file ''mip.lp'', we proceed as follows: In this example there are two integral variables ''x1'' and ''x2'', while ''s1'' and ''s2'' are continuous variables. Assuming the data is contained in the file ''mip.lp'', we proceed as follows:
 <code> <code>
-polytope > $m=lp2poly('mip.lp');+polytope > $m=lp2poly('demo/optimization_tut/mip.lp');
 polytope > $p = new Polytope<Rational>($m); polytope > $p = new Polytope<Rational>($m);
 </code> </code>
Line 322: Line 311:
 ===== Integral Polytopes and Total Unimodularity ===== ===== Integral Polytopes and Total Unimodularity =====
  
-As explained in the previous example, the integral points in a polytope are of particular interest in discrete optimization. These points are called //lattice points// in polymake and the corresponding convex hull //lattice polytope//. The handling of such polytopes is explained in more detail in the [[tutorial:lattice_polytopes_tutorial|Tutorial for Lattice Polytopes]].+As explained in the previous example, the integral points in a polytope are of particular interest in discrete optimization. These points are called //lattice points// in polymake and the corresponding convex hull //lattice polytope//. The handling of such polytopes is explained in more detail in the [[user_guide:tutorials:lattice_polytopes_tutorial|Tutorial for Lattice Polytopes]].
  
 Of particular interest for discrete optimization are properties of the orginal inequality system to define a lattice polytope, i.e., a polytope such that all of its vertices are integral (this can be tested by checking the property ''LATTICE''). One particularly interesting case occurs if the matrix defining the polytope is //totally unimodular// and the right hand side is integral. Of particular interest for discrete optimization are properties of the orginal inequality system to define a lattice polytope, i.e., a polytope such that all of its vertices are integral (this can be tested by checking the property ''LATTICE''). One particularly interesting case occurs if the matrix defining the polytope is //totally unimodular// and the right hand side is integral.
Line 345: Line 334:
 In the second example, we reuse the file ''c3t'' from the example above. We read it into polymake: In the second example, we reuse the file ''c3t'' from the example above. We read it into polymake:
 <code> <code>
-polytope > $f=lp2poly('c3t.lp');+polytope > $f=lp2poly('demo/optimization_tut/c3t.lp');
 polytope > $p = new Polytope<Rational>($f); polytope > $p = new Polytope<Rational>($f);
 </code> </code>
Line 389: Line 378:
 Let us test whether the inequality system of this example is TDI. Thus, we first load the data as usual: Let us test whether the inequality system of this example is TDI. Thus, we first load the data as usual:
 <code> <code>
-polytope > $f = lp2poly('stab.lp');+polytope > $f = lp2poly('demo/optimization_tut/stab.lp');
 polytope > $p = new Polytope<Rational>($f); polytope > $p = new Polytope<Rational>($f);
 </code> </code>
Line 453: Line 442:
 As before we read in the file using ''lp2poly'': As before we read in the file using ''lp2poly'':
 <code> <code>
-polytope > $f = lp2poly('stab.lp');+polytope > $f = lp2poly('demo/optimization_tut/stab.lp');
 polytope > $p = new Polytope<Rational>($f); polytope > $p = new Polytope<Rational>($f);
 </code> </code>
  • user_guide/tutorials/optimization.txt
  • Last modified: 2019/02/04 22:55
  • by 127.0.0.1