In this section, we will show two examples. The first one shows how simple

 [SEC]sec_lp_basics[SEC] Basic LP Features

 it is to formalize and solve an LP problem in LEMON, while the second one

 shows how LEMON facilitates solving network optimization problems using LP

 The following example demonstrates how simple it is to formalize and solve

 solvers.

 an LP problem in LEMON. You can find the whole program in \ref lp_demo.cc.

 \code

 \dontinclude lp_demo.cc

   Lp lp;

 \skip Create

 \until }

   Lp::Col x1 = lp.addCol();

 \until }

   Lp::Col x2 = lp.addCol();

 \ref LpBase::Col "Lp::Col" type represents the columns, i.e. the (primal)

   lp.addRow(0 <= x1 + x2 <= 100);

 variables of the LP problem. The numerical operators can be used to form

   lp.addRow(2 * x1 <= x2 + 32);

 expressions from columns, which are required for specifying rows

 (constraints) and the objective function. Due to the suitable operator

   lp.colLowerBound(x1, 0);

 overloads, a problem can be described in C++ conveniently, directly as it is

   lp.colUpperBound(x2, 100);

   lp.max();

   lp.obj(10 * x1 + 6 * x2);

   lp.solve();

   std::cout << "Objective function value: " << lp.primal() << std::endl;

   std::cout << "x1 = " << lp.primal(x1) << std::endl;

   std::cout << "x2 = " << lp.primal(x2) << std::endl;

 \endcode

 \ref LpBase::Col "Lp::Col" type represents the variables in the LP problems,

 while \ref LpBase::Row "Lp::Row" represents the constraints. The numerical

 operators can be used to form expressions from columns and dual

 expressions from rows. Due to the suitable operator overloads,

 a problem can be described in C++ conveniently, directly as it is

 After specifying all the parameters of the problem, we can solve it using

 the \ref LpSolver::solve() "solve()" function. The status of the solution

 (namely OPTIMAL, UNBOUNDED, INFEASIBLE etc.) can be obtained using

 \ref LpSolver::primalType() "primalType()" and the results can be

 obtained using \ref LpSolver::primal() "primal()".

 The above problem has an optimal solution. If you execute this example,

 it will print out the following results.

 \code

   Objective function value: 67.5

   x1 = 7.5

   x2 = 10

 \endcode

 However, if you, for example, removed the lines that specify the rows,

 you would obtain an LP problem, for which the objective function value

 is unbounded over the feasible solutions. Thus the program would print

 out this line.

 \code

   Optimal solution found.

 \endcode

 If you would like to build linear expressions or constraints in more steps,

 then you can use the classes \ref LpBase::Expr "Lp::Expr" and

 \ref LpBase::Constr "Lp::Constr". For example, this line

 \code

   lp.addRow(x1 - 5 <= x2);

 \endcode

 can also be written as

 \code

   Lp::Expr e1, e2;

   e1 = x1;

   e1 -= 5;

   e2 = x2;

   Lp::Constr c = e1 <= e2;

   lp.addRow(c);

 \endcode

 These classes make it easy to build more complex expressions and constraints,

 e.g. using loops. For example, we can sum all the variables (columns) in an

 expression using the \ref LpBase::ColIt "Lp::ColIt" iterator, which can be

 used the same as node and arc iterators for graphs.

 \code

   Lp::Expr sum;

   for (Lp::ColIt col(lp); col != INVALID; ++col) {

     sum += col;

   }

 \endcode

 After solving the problem, you can query the value of any primal expression,

 not just the individual columns and the objective function.

 \todo Check this example after closing ticket #326.

 \code

   std::cout << lp.primal(sum) << std::endl;

 \endcode

 Of course, working with the dual problem is also supported by the LP

 interface. \ref LpBase::Row "Lp::Row" represents the rows, i.e. the dual

 variables of the LP problem.

 \code

   Lp::Row r = lp.addRow(x2 >= 3);

 \endcode

 The dual solutions of an LP problem can be obtained using the functions

 \ref LpSolver::dualType() "dualType()" and \ref LpSolver::dual "dual()"

 (after solving the problem).

 \code

   std::cout << lp.dual(r) << std::endl;

 \endcode

 \ref LpBase::DualExpr "Lp::DualExpr" can be used to build dual expressions

 from rows and \ref LpBase::RowIt "Lp::RowIt" can be used to list the rows.

 \code

   Lp::DualExpr dual_sum;

   for (Lp::RowIt row(lp); row != INVALID; ++row) {

     dual_sum += row;

   }

 \endcode

 The LP solver interface provides several other features, which are

 documented in the classes \ref LpBase and \ref LpSolver.

 For detailed documentation, see these classes in the reference manual.

 If you would like to use a specific solver instead of the default one,

 you can use \ref GlpkLp, \ref ClpLp, \ref CplexLp etc. instead of

 the class \ref Lp.

 [SEC]sec_lp_mip[SEC] Mixed Integer Programming

 LEMON also provides a similar high-level interface for mixed integer

 programming (MIP) solvers. The default MIP solver can be used through

 the class \ref Mip, while the concrete solvers are implemented in the

 classes \ref GlpkMip, \ref CbcMip, \ref CplexMip etc.

 The following example demonstrates the usage of the MIP solver interface.

 The whole program can be found in \ref mip_demo.cc.

 \dontinclude mip_demo.cc

 \skip Create

 \until }

 \until }

 \todo Check this demo file after closing ticket #326.

 E.g. could we write <tt>mip.sol()</tt> instead of <tt>mip.solValue()</tt>?

 Or could we write <tt>primalValue()</tt> for \c Lp in \c lp_demo.cc?

 In this program, the same problem is built as in the above example,

 with the exception that the variable \c x1 is specified to be

 \c INTEGER valued. \c x2 is set to \c REAL, which is the default option.

 \code

   // Set the type of the columns

   mip.colType(x1, Mip::INTEGER);

   mip.colType(x2, Mip::REAL);

 \endcode

 Because of this integrality requirement, the results will be different

 from the LP solution.

 \code

   Objective function value: 67

   x1 = 8

   x2 = 9

 \endcode

 The documnetation of the MIP solver interface can be found in the

 reference manual at the class \ref MipSolver. The common parts of the

 LP and MIP interfaces are docmented in their common ancestor class

 \ref LpBase.

 [SEC]sec_lp_optimization[SEC] Solving Complex Optimization Problems

 The LP and MIP solvers are powerful tools for solving various complex

 optimization problems, as well.

 programming. Several other graph optimization problems can also be

 programming, see the whole program in \re lp_maxflow_demo.cc.

 expressed as linear programs and this interface helps to solve them easily

 Several other graph optimization problems can also be expressed as

 (though usually not so efficiently as by a direct combinatorial method).

 linear programs and the interface provided in LEMON facilitates solving

 them easily (though usually not so efficiently as by a direct

 \code

 combinatorial method, if one exists). 

   Lp lp;

   ListDigraph::ArcMap<Lp::Col> f(g);

 \dontinclude lp_maxflow_demo.cc

   lp.addColSet(f);

 \skip DIGRAPH_TYPEDEFS

 \until solve()

   // Capacity constraints

   for (ListDigraph::ArcIt a(g); a != INVALID; ++a) {

 \note This problem can be solved much more efficiently using common

     lp.colLowerBound(f[a], 0);

 combinatorial optimization methods, such as the \ref Preflow

     lp.colUpperBound(f[a], capacity[a]);

 "preflow push-relabel algorithm".

   }

   // Flow conservation constraints

   for (ListDigraph::NodeIt n(g); n != INVALID; ++n) {

     if (n == src || n == trg) continue;

     Lp::Expr e;

     for (ListDigraph::OutArcIt a(g,n); a != INVALID; ++a) e += f[a];

     for (ListDigraph::InArcIt a(g,n); a != INVALID; ++a) e -= f[a];

     lp.addRow(e == 0);

   }

   // Objective function

   Lp::Expr o;

   for (ListDigraph::OutArcIt a(g,src); a != INVALID; ++a) o += f[a];

   for (ListDigraph::InArcIt a(g,src); a != INVALID; ++a) o -= f[a];

   lp.max();

   lp.obj(o);

   lp.solve();

   std::cout << "Max flow value: " << lp.primal() << std::endl;

 \endcode