COIN-OR::LEMON - Graph Library

Changeset 1517:b303c1741c9a in lemon-0.x for doc/quicktour.dox


Ignore:
Timestamp:
06/27/05 17:22:34 (14 years ago)
Author:
athos
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2002
Message:

Some modifications in this and that.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/quicktour.dox

    r1514 r1517  
    142142Ide Zsuzska fog irni!
    143143
    144 <li>Many problems in network optimization can be formalized by means of a
    145 linear programming problem (LP problem, for short). In our library we decided
    146 not to write an LP solver, since such packages are available in the commercial
    147 world just as well as in the open source world, and it is also a difficult
    148 task to compete these. Instead we decided to develop an interface that makes
    149 it easier to use these solvers together with LEMON. So far we have an
     144<li>Many problems in network optimization can be formalized by means
     145of a linear programming problem (LP problem, for short). In our
     146library we decided not to write an LP solver, since such packages are
     147available in the commercial world just as well as in the open source
     148world, and it is also a difficult task to compete these. Instead we
     149decided to develop an interface that makes it easier to use these
     150solvers together with LEMON. The advantage of this approach is
     151twofold. Firstly our C++ interface is more comfortable than the
     152solvers' native interface. Secondly, changing the underlying solver in
     153a certain software using LEMON's LP interface needs zero effort. So,
     154for example, one may try his idea using a free solver, demonstrate its
     155usability for a customer and if it works well, but the performance
     156should be improved, then one may decide to purchase and use a better
     157commercial solver.
     158
     159So far we have an
    150160interface for the commercial LP solver software \b CLPLEX (developed by ILOG)
    151161and for the open source solver \b GLPK (a shorthand for Gnu Linear Programming
    152 Toolkit). 
     162Toolkit).
    153163
    154164We will show two examples, the first one shows how simple it is to formalize
     
    158168<ol>
    159169<li>The following code shows how to solve an LP problem using the LEMON lp
    160 interface.
     170interface. The code together with the comments is self-explanatory.
    161171
    162172\code
     
    205215See the whole code in \ref lp_demo.cc.
    206216
    207 <li>The second example shows how easy it is to formalize a network
    208 optimization problem as an LP problem using the LEMON LP interface.
     217<li>The second example shows how easy it is to formalize a max-flow
     218problem as an LP problem using the LEMON LP interface: we are looking
     219for a real valued function defined on the edges of the digraph
     220satisfying the nonnegativity-, the capacity constraints and the
     221flow-conservation constraints and giving the largest flow value
     222between to designated nodes.
     223
     224In the following code we suppose that we already have the graph \c g,
     225the capacity map \c cap, the source node \c s and the target node \c t
     226in the memory. We will also omit the typedefs.
     227
     228\code
     229  //Define a map on the edges for the variables of the LP problem
     230  typename G::template EdgeMap<LpDefault::Col> x(g);
     231  lp.addColSet(x);
     232 
     233  //Nonnegativity and capacity constraints
     234  for(EdgeIt e(g);e!=INVALID;++e) {
     235    lp.colUpperBound(x[e],cap[e]);
     236    lp.colLowerBound(x[e],0);
     237  }
     238
     239
     240  //Flow conservation constraints for the nodes (except for 's' and 't')
     241  for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) {
     242    LpDefault::Expr ex;
     243    for(InEdgeIt  e(g,n);e!=INVALID;++e) ex+=x[e];
     244    for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e];
     245    lp.addRow(ex==0);
     246  }
     247 
     248  //Objective function: the flow value entering 't'
     249  {
     250    LpDefault::Expr ex;
     251    for(InEdgeIt  e(g,t);e!=INVALID;++e) ex+=x[e];
     252    for(OutEdgeIt e(g,t);e!=INVALID;++e) ex-=x[e];
     253    lp.setObj(ex);
     254  }
     255
     256  //Maximization
     257  lp.max();
     258
     259  //Solve with the underlying solver
     260  lp.solve();
     261
     262\endcode
     263
     264The complete program can be found in file \ref lp_maxflow_demo.cc. After compiling run it in the form:
     265
     266<tt>./lp_maxflow_demo < ?????????.lgf</tt>
     267
     268where ?????????.lgf is a file in the lemon format containing a maxflow instance (designated "source", "target" nodes and "capacity" map).
     269
     270
     271See the whole code in \ref lp_demo.cc.
     272
    209273
    210274</ol>
Note: See TracChangeset for help on using the changeset viewer.