1.1 --- a/doc/quicktour.dox Mon Jun 27 14:39:53 2005 +0000
1.2 +++ b/doc/quicktour.dox Mon Jun 27 15:22:34 2005 +0000
1.3 @@ -141,15 +141,25 @@
1.4
1.5 Ide Zsuzska fog irni!
1.6
1.7 -<li>Many problems in network optimization can be formalized by means of a
1.8 -linear programming problem (LP problem, for short). In our library we decided
1.9 -not to write an LP solver, since such packages are available in the commercial
1.10 -world just as well as in the open source world, and it is also a difficult
1.11 -task to compete these. Instead we decided to develop an interface that makes
1.12 -it easier to use these solvers together with LEMON. So far we have an
1.13 +<li>Many problems in network optimization can be formalized by means
1.14 +of a linear programming problem (LP problem, for short). In our
1.15 +library we decided not to write an LP solver, since such packages are
1.16 +available in the commercial world just as well as in the open source
1.17 +world, and it is also a difficult task to compete these. Instead we
1.18 +decided to develop an interface that makes it easier to use these
1.19 +solvers together with LEMON. The advantage of this approach is
1.20 +twofold. Firstly our C++ interface is more comfortable than the
1.21 +solvers' native interface. Secondly, changing the underlying solver in
1.22 +a certain software using LEMON's LP interface needs zero effort. So,
1.23 +for example, one may try his idea using a free solver, demonstrate its
1.24 +usability for a customer and if it works well, but the performance
1.25 +should be improved, then one may decide to purchase and use a better
1.26 +commercial solver.
1.27 +
1.28 +So far we have an
1.29 interface for the commercial LP solver software \b CLPLEX (developed by ILOG)
1.30 and for the open source solver \b GLPK (a shorthand for Gnu Linear Programming
1.31 -Toolkit).
1.32 +Toolkit).
1.33
1.34 We will show two examples, the first one shows how simple it is to formalize
1.35 and solve an LP problem in LEMON, while the second one shows how LEMON
1.36 @@ -157,7 +167,7 @@
1.37
1.38 <ol>
1.39 <li>The following code shows how to solve an LP problem using the LEMON lp
1.40 -interface.
1.41 +interface. The code together with the comments is self-explanatory.
1.42
1.43 \code
1.44
1.45 @@ -204,8 +214,62 @@
1.46
1.47 See the whole code in \ref lp_demo.cc.
1.48
1.49 -<li>The second example shows how easy it is to formalize a network
1.50 -optimization problem as an LP problem using the LEMON LP interface.
1.51 +<li>The second example shows how easy it is to formalize a max-flow
1.52 +problem as an LP problem using the LEMON LP interface: we are looking
1.53 +for a real valued function defined on the edges of the digraph
1.54 +satisfying the nonnegativity-, the capacity constraints and the
1.55 +flow-conservation constraints and giving the largest flow value
1.56 +between to designated nodes.
1.57 +
1.58 +In the following code we suppose that we already have the graph \c g,
1.59 +the capacity map \c cap, the source node \c s and the target node \c t
1.60 +in the memory. We will also omit the typedefs.
1.61 +
1.62 +\code
1.63 + //Define a map on the edges for the variables of the LP problem
1.64 + typename G::template EdgeMap<LpDefault::Col> x(g);
1.65 + lp.addColSet(x);
1.66 +
1.67 + //Nonnegativity and capacity constraints
1.68 + for(EdgeIt e(g);e!=INVALID;++e) {
1.69 + lp.colUpperBound(x[e],cap[e]);
1.70 + lp.colLowerBound(x[e],0);
1.71 + }
1.72 +
1.73 +
1.74 + //Flow conservation constraints for the nodes (except for 's' and 't')
1.75 + for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) {
1.76 + LpDefault::Expr ex;
1.77 + for(InEdgeIt e(g,n);e!=INVALID;++e) ex+=x[e];
1.78 + for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e];
1.79 + lp.addRow(ex==0);
1.80 + }
1.81 +
1.82 + //Objective function: the flow value entering 't'
1.83 + {
1.84 + LpDefault::Expr ex;
1.85 + for(InEdgeIt e(g,t);e!=INVALID;++e) ex+=x[e];
1.86 + for(OutEdgeIt e(g,t);e!=INVALID;++e) ex-=x[e];
1.87 + lp.setObj(ex);
1.88 + }
1.89 +
1.90 + //Maximization
1.91 + lp.max();
1.92 +
1.93 + //Solve with the underlying solver
1.94 + lp.solve();
1.95 +
1.96 +\endcode
1.97 +
1.98 +The complete program can be found in file \ref lp_maxflow_demo.cc. After compiling run it in the form:
1.99 +
1.100 +<tt>./lp_maxflow_demo < ?????????.lgf</tt>
1.101 +
1.102 +where ?????????.lgf is a file in the lemon format containing a maxflow instance (designated "source", "target" nodes and "capacity" map).
1.103 +
1.104 +
1.105 +See the whole code in \ref lp_demo.cc.
1.106 +
1.107
1.108 </ol>
1.109 </ul>