1.1 --- a/lp.dox	Mon Mar 01 02:26:24 2010 +0100
     1.2 +++ b/lp.dox	Mon Mar 01 02:27:36 2010 +0100
     1.3 @@ -44,76 +44,181 @@
     1.4  However, additional wrapper classes for new solvers can also be implemented
     1.5  quite easily.
     1.6  
     1.7 -In this section, we will show two examples. The first one shows how simple
     1.8 -it is to formalize and solve an LP problem in LEMON, while the second one
     1.9 -shows how LEMON facilitates solving network optimization problems using LP
    1.10 -solvers.
    1.11 +[SEC]sec_lp_basics[SEC] Basic LP Features
    1.12 +
    1.13 +The following example demonstrates how simple it is to formalize and solve
    1.14 +an LP problem in LEMON. You can find the whole program in \ref lp_demo.cc.
    1.15 +
    1.16 +\dontinclude lp_demo.cc
    1.17 +\skip Create
    1.18 +\until }
    1.19 +\until }
    1.20 +
    1.21 +\ref LpBase::Col "Lp::Col" type represents the columns, i.e. the (primal)
    1.22 +variables of the LP problem. The numerical operators can be used to form
    1.23 +expressions from columns, which are required for specifying rows
    1.24 +(constraints) and the objective function. Due to the suitable operator
    1.25 +overloads, a problem can be described in C++ conveniently, directly as it is
    1.26 +expressed in mathematics.
    1.27 +After specifying all the parameters of the problem, we can solve it using
    1.28 +the \ref LpSolver::solve() "solve()" function. The status of the solution
    1.29 +(namely OPTIMAL, UNBOUNDED, INFEASIBLE etc.) can be obtained using
    1.30 +\ref LpSolver::primalType() "primalType()" and the results can be
    1.31 +obtained using \ref LpSolver::primal() "primal()".
    1.32 +
    1.33 +The above problem has an optimal solution. If you execute this example,
    1.34 +it will print out the following results.
    1.35  
    1.36  \code
    1.37 -  Lp lp;
    1.38 -
    1.39 -  Lp::Col x1 = lp.addCol();
    1.40 -  Lp::Col x2 = lp.addCol();
    1.41 -
    1.42 -  lp.addRow(0 <= x1 + x2 <= 100);
    1.43 -  lp.addRow(2 * x1 <= x2 + 32);
    1.44 -
    1.45 -  lp.colLowerBound(x1, 0);
    1.46 -  lp.colUpperBound(x2, 100);
    1.47 -
    1.48 -  lp.max();
    1.49 -  lp.obj(10 * x1 + 6 * x2);
    1.50 -  lp.solve();
    1.51 -
    1.52 -  std::cout << "Objective function value: " << lp.primal() << std::endl;
    1.53 -  std::cout << "x1 = " << lp.primal(x1) << std::endl;
    1.54 -  std::cout << "x2 = " << lp.primal(x2) << std::endl;
    1.55 +  Objective function value: 67.5
    1.56 +  x1 = 7.5
    1.57 +  x2 = 10
    1.58  \endcode
    1.59  
    1.60 -\ref LpBase::Col "Lp::Col" type represents the variables in the LP problems,
    1.61 -while \ref LpBase::Row "Lp::Row" represents the constraints. The numerical
    1.62 -operators can be used to form expressions from columns and dual
    1.63 -expressions from rows. Due to the suitable operator overloads,
    1.64 -a problem can be described in C++ conveniently, directly as it is
    1.65 -expressed in mathematics.
    1.66 -
    1.67 -The following example solves a maximum flow problem with linear
    1.68 -programming. Several other graph optimization problems can also be
    1.69 -expressed as linear programs and this interface helps to solve them easily
    1.70 -(though usually not so efficiently as by a direct combinatorial method).
    1.71 +However, if you, for example, removed the lines that specify the rows,
    1.72 +you would obtain an LP problem, for which the objective function value
    1.73 +is unbounded over the feasible solutions. Thus the program would print
    1.74 +out this line.
    1.75  
    1.76  \code
    1.77 -  Lp lp;
    1.78 -  ListDigraph::ArcMap<Lp::Col> f(g);
    1.79 -  lp.addColSet(f);
    1.80 +  Optimal solution found.
    1.81 +\endcode
    1.82  
    1.83 -  // Capacity constraints
    1.84 -  for (ListDigraph::ArcIt a(g); a != INVALID; ++a) {
    1.85 -    lp.colLowerBound(f[a], 0);
    1.86 -    lp.colUpperBound(f[a], capacity[a]);
    1.87 +If you would like to build linear expressions or constraints in more steps,
    1.88 +then you can use the classes \ref LpBase::Expr "Lp::Expr" and
    1.89 +\ref LpBase::Constr "Lp::Constr". For example, this line
    1.90 +\code
    1.91 +  lp.addRow(x1 - 5 <= x2);
    1.92 +\endcode
    1.93 +can also be written as
    1.94 +\code
    1.95 +  Lp::Expr e1, e2;
    1.96 +  e1 = x1;
    1.97 +  e1 -= 5;
    1.98 +  e2 = x2;
    1.99 +  Lp::Constr c = e1 <= e2;
   1.100 +  lp.addRow(c);
   1.101 +\endcode
   1.102 +
   1.103 +These classes make it easy to build more complex expressions and constraints,
   1.104 +e.g. using loops. For example, we can sum all the variables (columns) in an
   1.105 +expression using the \ref LpBase::ColIt "Lp::ColIt" iterator, which can be
   1.106 +used the same as node and arc iterators for graphs.
   1.107 +
   1.108 +\code
   1.109 +  Lp::Expr sum;
   1.110 +  for (Lp::ColIt col(lp); col != INVALID; ++col) {
   1.111 +    sum += col;
   1.112    }
   1.113 +\endcode
   1.114  
   1.115 -  // Flow conservation constraints
   1.116 -  for (ListDigraph::NodeIt n(g); n != INVALID; ++n) {
   1.117 -    if (n == src || n == trg) continue;
   1.118 -    Lp::Expr e;
   1.119 -    for (ListDigraph::OutArcIt a(g,n); a != INVALID; ++a) e += f[a];
   1.120 -    for (ListDigraph::InArcIt a(g,n); a != INVALID; ++a) e -= f[a];
   1.121 -    lp.addRow(e == 0);
   1.122 +After solving the problem, you can query the value of any primal expression,
   1.123 +not just the individual columns and the objective function.
   1.124 +
   1.125 +\todo Check this example after closing ticket #326.
   1.126 +
   1.127 +\code
   1.128 +  std::cout << lp.primal(sum) << std::endl;
   1.129 +\endcode
   1.130 +
   1.131 +Of course, working with the dual problem is also supported by the LP
   1.132 +interface. \ref LpBase::Row "Lp::Row" represents the rows, i.e. the dual
   1.133 +variables of the LP problem.
   1.134 +
   1.135 +\code
   1.136 +  Lp::Row r = lp.addRow(x2 >= 3);
   1.137 +\endcode
   1.138 +
   1.139 +The dual solutions of an LP problem can be obtained using the functions
   1.140 +\ref LpSolver::dualType() "dualType()" and \ref LpSolver::dual "dual()"
   1.141 +(after solving the problem).
   1.142 +
   1.143 +\code
   1.144 +  std::cout << lp.dual(r) << std::endl;
   1.145 +\endcode
   1.146 +
   1.147 +\ref LpBase::DualExpr "Lp::DualExpr" can be used to build dual expressions
   1.148 +from rows and \ref LpBase::RowIt "Lp::RowIt" can be used to list the rows.
   1.149 +
   1.150 +\code
   1.151 +  Lp::DualExpr dual_sum;
   1.152 +  for (Lp::RowIt row(lp); row != INVALID; ++row) {
   1.153 +    dual_sum += row;
   1.154    }
   1.155 +\endcode
   1.156  
   1.157 -  // Objective function
   1.158 -  Lp::Expr o;
   1.159 -  for (ListDigraph::OutArcIt a(g,src); a != INVALID; ++a) o += f[a];
   1.160 -  for (ListDigraph::InArcIt a(g,src); a != INVALID; ++a) o -= f[a];
   1.161 +The LP solver interface provides several other features, which are
   1.162 +documented in the classes \ref LpBase and \ref LpSolver.
   1.163 +For detailed documentation, see these classes in the reference manual.
   1.164  
   1.165 -  lp.max();
   1.166 -  lp.obj(o);
   1.167 -  lp.solve();
   1.168 +If you would like to use a specific solver instead of the default one,
   1.169 +you can use \ref GlpkLp, \ref ClpLp, \ref CplexLp etc. instead of
   1.170 +the class \ref Lp.
   1.171  
   1.172 -  std::cout << "Max flow value: " << lp.primal() << std::endl;
   1.173 +
   1.174 +[SEC]sec_lp_mip[SEC] Mixed Integer Programming
   1.175 +
   1.176 +LEMON also provides a similar high-level interface for mixed integer
   1.177 +programming (MIP) solvers. The default MIP solver can be used through
   1.178 +the class \ref Mip, while the concrete solvers are implemented in the
   1.179 +classes \ref GlpkMip, \ref CbcMip, \ref CplexMip etc.
   1.180 +
   1.181 +The following example demonstrates the usage of the MIP solver interface.
   1.182 +The whole program can be found in \ref mip_demo.cc.
   1.183 +
   1.184 +\dontinclude mip_demo.cc
   1.185 +\skip Create
   1.186 +\until }
   1.187 +\until }
   1.188 +
   1.189 +\todo Check this demo file after closing ticket #326.
   1.190 +E.g. could we write <tt>mip.sol()</tt> instead of <tt>mip.solValue()</tt>?
   1.191 +Or could we write <tt>primalValue()</tt> for \c Lp in \c lp_demo.cc?
   1.192 +
   1.193 +In this program, the same problem is built as in the above example,
   1.194 +with the exception that the variable \c x1 is specified to be
   1.195 +\c INTEGER valued. \c x2 is set to \c REAL, which is the default option.
   1.196 +
   1.197 +\code
   1.198 +  // Set the type of the columns
   1.199 +  mip.colType(x1, Mip::INTEGER);
   1.200 +  mip.colType(x2, Mip::REAL);
   1.201  \endcode
   1.202  
   1.203 +Because of this integrality requirement, the results will be different
   1.204 +from the LP solution.
   1.205 +
   1.206 +\code
   1.207 +  Objective function value: 67
   1.208 +  x1 = 8
   1.209 +  x2 = 9
   1.210 +\endcode
   1.211 +
   1.212 +The documnetation of the MIP solver interface can be found in the
   1.213 +reference manual at the class \ref MipSolver. The common parts of the
   1.214 +LP and MIP interfaces are docmented in their common ancestor class
   1.215 +\ref LpBase.
   1.216 +
   1.217 +
   1.218 +[SEC]sec_lp_optimization[SEC] Solving Complex Optimization Problems
   1.219 +
   1.220 +The LP and MIP solvers are powerful tools for solving various complex
   1.221 +optimization problems, as well.
   1.222 +The following example solves a maximum flow problem with linear
   1.223 +programming, see the whole program in \re lp_maxflow_demo.cc.
   1.224 +Several other graph optimization problems can also be expressed as
   1.225 +linear programs and the interface provided in LEMON facilitates solving
   1.226 +them easily (though usually not so efficiently as by a direct
   1.227 +combinatorial method, if one exists). 
   1.228 +
   1.229 +\dontinclude lp_maxflow_demo.cc
   1.230 +\skip DIGRAPH_TYPEDEFS
   1.231 +\until solve()
   1.232 +
   1.233 +\note This problem can be solved much more efficiently using common
   1.234 +combinatorial optimization methods, such as the \ref Preflow
   1.235 +"preflow push-relabel algorithm".
   1.236 +
   1.237  [TRAILER]
   1.238  */
   1.239  }

     2.1 --- a/toc.txt	Mon Mar 01 02:26:24 2010 +0100
     2.2 +++ b/toc.txt	Mon Mar 01 02:27:36 2010 +0100
     2.3 @@ -33,6 +33,9 @@
     2.4  ** sec_subgraphs
     2.5  ** sec_other_adaptors
     2.6  * sec_lp
     2.7 +** sec_lp_basics
     2.8 +** sec_lp_mip
     2.9 +** sec_lp_optimization
    2.10  * sec_lgf
    2.11  * sec_tools
    2.12  ** sec_aux_structures