Index: lp.dox
===================================================================
--- lp.dox (revision 50)
+++ lp.dox (revision 55)
@@ -45,73 +45,178 @@
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.
-
-\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;
-\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
+[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
+ 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 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. 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).
-
-\code
- Lp lp;
- ListDigraph::ArcMap f(g);
- lp.addColSet(f);
-
- // Capacity constraints
- for (ListDigraph::ArcIt a(g); a != INVALID; ++a) {
- lp.colLowerBound(f[a], 0);
- lp.colUpperBound(f[a], capacity[a]);
- }
-
- // 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
+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]