# HG changeset patch # User Peter Kovacs # Date 1267406856 -3600 # Node ID edb7d5759e0d57f2600dfc752a8f7a2fe20a0988 # Parent e99a7fb6bff536620b05d23509457ced4ec88ba5 Greatly extend LP section diff -r e99a7fb6bff5 -r edb7d5759e0d lp.dox --- a/lp.dox Mon Mar 01 02:26:24 2010 +0100 +++ b/lp.dox Mon Mar 01 02:27:36 2010 +0100 @@ -44,76 +44,181 @@ However, additional wrapper classes for new solvers can also be implemented quite easily. -In this section, we will show two examples. The first one shows how simple -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 -solvers. +[SEC]sec_lp_basics[SEC] Basic LP Features + +The following example demonstrates how simple it is to formalize and solve +an LP problem in LEMON. You can find the whole program in \ref lp_demo.cc. + +\dontinclude lp_demo.cc +\skip Create +\until } +\until } + +\ref LpBase::Col "Lp::Col" type represents the columns, i.e. the (primal) +variables of the LP problem. The numerical operators can be used to form +expressions from columns, which are required for specifying rows +(constraints) and the objective function. Due to the suitable operator +overloads, a problem can be described in C++ conveniently, directly as it is +expressed in mathematics. +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 - Lp lp; - - Lp::Col x1 = lp.addCol(); - Lp::Col x2 = lp.addCol(); - - lp.addRow(0 <= x1 + x2 <= 100); - lp.addRow(2 * x1 <= x2 + 32); - - lp.colLowerBound(x1, 0); - 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; + Objective function value: 67.5 + x1 = 7.5 + x2 = 10 \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 -expressed in mathematics. - -The following example solves a maximum flow problem with linear -programming. Several other graph optimization problems can also be -expressed as linear programs and this interface helps to solve them easily -(though usually not so efficiently as by a direct combinatorial method). +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 - Lp lp; - ListDigraph::ArcMap f(g); - lp.addColSet(f); + Optimal solution found. +\endcode - // Capacity constraints - for (ListDigraph::ArcIt a(g); a != INVALID; ++a) { - lp.colLowerBound(f[a], 0); - lp.colUpperBound(f[a], capacity[a]); +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 - // 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); +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 - // 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]; +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. - lp.max(); - lp.obj(o); - lp.solve(); +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. - std::cout << "Max flow value: " << lp.primal() << std::endl; + +[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 mip.sol() instead of mip.solValue()? +Or could we write primalValue() 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. +The following example solves a maximum flow problem with linear +programming, see the whole program in \re lp_maxflow_demo.cc. +Several other graph optimization problems can also be expressed as +linear programs and the interface provided in LEMON facilitates solving +them easily (though usually not so efficiently as by a direct +combinatorial method, if one exists). + +\dontinclude lp_maxflow_demo.cc +\skip DIGRAPH_TYPEDEFS +\until solve() + +\note This problem can be solved much more efficiently using common +combinatorial optimization methods, such as the \ref Preflow +"preflow push-relabel algorithm". + [TRAILER] */ } diff -r e99a7fb6bff5 -r edb7d5759e0d toc.txt --- a/toc.txt Mon Mar 01 02:26:24 2010 +0100 +++ b/toc.txt Mon Mar 01 02:27:36 2010 +0100 @@ -33,6 +33,9 @@ ** sec_subgraphs ** sec_other_adaptors * sec_lp +** sec_lp_basics +** sec_lp_mip +** sec_lp_optimization * sec_lgf * sec_tools ** sec_aux_structures