Changeset 55:edb7d5759e0d in lemon-tutorial

Timestamp:

03/01/10 02:27:36 (15 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Greatly extend LP section

Files:

• lp.dox (modified) (1 diff)
• toc.txt (modified) (1 diff)

lp.dox

@@ -45 +45 @@
 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 <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.
 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<Lp::Col> 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]

toc.txt

@@ -34 +34 @@
 ** sec_other_adaptors
 * sec_lp
+** sec_lp_basics
+** sec_lp_mip
+** sec_lp_optimization
 * sec_lgf
 * sec_tools