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