<li>Many problems in network optimization can be formalized by means of a

 <li>Many problems in network optimization can be formalized by means

 linear programming problem (LP problem, for short). In our library we decided

 of a linear programming problem (LP problem, for short). In our

 not to write an LP solver, since such packages are available in the commercial

 library we decided not to write an LP solver, since such packages are

 world just as well as in the open source world, and it is also a difficult

 available in the commercial world just as well as in the open source

 task to compete these. Instead we decided to develop an interface that makes

 world, and it is also a difficult task to compete these. Instead we

 it easier to use these solvers together with LEMON. So far we have an

 decided to develop an interface that makes it easier to use these

 solvers together with LEMON. The advantage of this approach is

 twofold. Firstly our C++ interface is more comfortable than the

 solvers' native interface. Secondly, changing the underlying solver in

 a certain software using LEMON's LP interface needs zero effort. So,

 for example, one may try his idea using a free solver, demonstrate its

 usability for a customer and if it works well, but the performance

 should be improved, then one may decide to purchase and use a better

 commercial solver.

 So far we have an

 Toolkit). 

 Toolkit).

 interface. 

 interface. The code together with the comments is self-explanatory.

 <li>The second example shows how easy it is to formalize a network

 <li>The second example shows how easy it is to formalize a max-flow

 optimization problem as an LP problem using the LEMON LP interface.

 problem as an LP problem using the LEMON LP interface: we are looking

 for a real valued function defined on the edges of the digraph

 satisfying the nonnegativity-, the capacity constraints and the

 flow-conservation constraints and giving the largest flow value

 between to designated nodes.

 In the following code we suppose that we already have the graph \c g,

 the capacity map \c cap, the source node \c s and the target node \c t

 in the memory. We will also omit the typedefs.

 \code

   //Define a map on the edges for the variables of the LP problem

   typename G::template EdgeMap<LpDefault::Col> x(g);

   lp.addColSet(x);

   //Nonnegativity and capacity constraints

   for(EdgeIt e(g);e!=INVALID;++e) {

     lp.colUpperBound(x[e],cap[e]);

     lp.colLowerBound(x[e],0);

   }

   //Flow conservation constraints for the nodes (except for 's' and 't')

   for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) {

     LpDefault::Expr ex;

     for(InEdgeIt  e(g,n);e!=INVALID;++e) ex+=x[e];

     for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e];

     lp.addRow(ex==0);

   }

   //Objective function: the flow value entering 't'

   {

     LpDefault::Expr ex;

     for(InEdgeIt  e(g,t);e!=INVALID;++e) ex+=x[e];

     for(OutEdgeIt e(g,t);e!=INVALID;++e) ex-=x[e];

     lp.setObj(ex);

   }

   //Maximization

   lp.max();

   //Solve with the underlying solver

   lp.solve();

 \endcode

 The complete program can be found in file \ref lp_maxflow_demo.cc. After compiling run it in the form:

 <tt>./lp_maxflow_demo < ?????????.lgf</tt>

 where ?????????.lgf is a file in the lemon format containing a maxflow instance (designated "source", "target" nodes and "capacity" map).

 See the whole code in \ref lp_demo.cc.