[30] | 1 | /* -*- mode: C++; indent-tabs-mode: nil; -*- |
---|
| 2 | * |
---|
| 3 | * This file is a part of LEMON, a generic C++ optimization library. |
---|
| 4 | * |
---|
[32] | 5 | * Copyright (C) 2003-2010 |
---|
[30] | 6 | * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
---|
| 7 | * (Egervary Research Group on Combinatorial Optimization, EGRES). |
---|
| 8 | * |
---|
| 9 | * Permission to use, modify and distribute this software is granted |
---|
| 10 | * provided that this copyright notice appears in all copies. For |
---|
| 11 | * precise terms see the accompanying LICENSE file. |
---|
| 12 | * |
---|
| 13 | * This software is provided "AS IS" with no warranty of any kind, |
---|
| 14 | * express or implied, and with no claim as to its suitability for any |
---|
| 15 | * purpose. |
---|
| 16 | * |
---|
| 17 | */ |
---|
| 18 | |
---|
| 19 | namespace lemon { |
---|
| 20 | /** |
---|
| 21 | [PAGE]sec_lp[PAGE] Linear Programming Interface |
---|
| 22 | |
---|
[48] | 23 | Linear programming (LP) is one of the most important general methods of |
---|
| 24 | operations research. Countless optimization problems can be formulated |
---|
| 25 | and solved using LP techniques. |
---|
| 26 | Therefore, developing efficient LP solvers has been of high practical |
---|
| 27 | interest for a long time. |
---|
| 28 | Nowadays various efficient LP solvers are available, including both |
---|
| 29 | open source and commercial software packages. |
---|
| 30 | Therefore, LEMON does not implement its own solver, but it features |
---|
| 31 | wrapper classes for several known LP packages providing a common |
---|
| 32 | high-level interface for all of them. |
---|
[30] | 33 | |
---|
[48] | 34 | The advantage of this approach is twofold. First, our C++ interface is |
---|
| 35 | more comfortable than the typical native interfaces of the solvers. |
---|
| 36 | Second, changing the underlying solver in a certain application using |
---|
| 37 | LEMON's LP interface needs no effort. So, for example, one may try her |
---|
| 38 | idea using an open source solver, demonstrate its usability for a customer |
---|
| 39 | and if it works well, but the performance should be improved, then the |
---|
| 40 | customer may decide to purchase and use a better commercial solver. |
---|
| 41 | |
---|
| 42 | Currently, the following linear and mixed integer programming packages are |
---|
| 43 | supported: GLPK, Clp, Cbc, ILOG CPLEX and SoPlex. |
---|
| 44 | However, additional wrapper classes for new solvers can also be implemented |
---|
| 45 | quite easily. |
---|
| 46 | |
---|
[55] | 47 | [SEC]sec_lp_basics[SEC] Basic LP Features |
---|
| 48 | |
---|
| 49 | The following example demonstrates how simple it is to formalize and solve |
---|
| 50 | an LP problem in LEMON. You can find the whole program in \ref lp_demo.cc. |
---|
| 51 | |
---|
| 52 | \dontinclude lp_demo.cc |
---|
| 53 | \skip Create |
---|
| 54 | \until } |
---|
| 55 | \until } |
---|
| 56 | |
---|
| 57 | \ref LpBase::Col "Lp::Col" type represents the columns, i.e. the (primal) |
---|
| 58 | variables of the LP problem. The numerical operators can be used to form |
---|
| 59 | expressions from columns, which are required for specifying rows |
---|
| 60 | (constraints) and the objective function. Due to the suitable operator |
---|
| 61 | overloads, a problem can be described in C++ conveniently, directly as it is |
---|
| 62 | expressed in mathematics. |
---|
| 63 | After specifying all the parameters of the problem, we can solve it using |
---|
| 64 | the \ref LpSolver::solve() "solve()" function. The status of the solution |
---|
| 65 | (namely OPTIMAL, UNBOUNDED, INFEASIBLE etc.) can be obtained using |
---|
| 66 | \ref LpSolver::primalType() "primalType()" and the results can be |
---|
| 67 | obtained using \ref LpSolver::primal() "primal()". |
---|
| 68 | |
---|
| 69 | The above problem has an optimal solution. If you execute this example, |
---|
| 70 | it will print out the following results. |
---|
[30] | 71 | |
---|
| 72 | \code |
---|
[55] | 73 | Objective function value: 67.5 |
---|
| 74 | x1 = 7.5 |
---|
| 75 | x2 = 10 |
---|
[30] | 76 | \endcode |
---|
| 77 | |
---|
[55] | 78 | However, if you, for example, removed the lines that specify the rows, |
---|
| 79 | you would obtain an LP problem, for which the objective function value |
---|
| 80 | is unbounded over the feasible solutions. Thus the program would print |
---|
| 81 | out this line. |
---|
[30] | 82 | |
---|
| 83 | \code |
---|
[55] | 84 | Optimal solution found. |
---|
| 85 | \endcode |
---|
[30] | 86 | |
---|
[55] | 87 | If you would like to build linear expressions or constraints in more steps, |
---|
| 88 | then you can use the classes \ref LpBase::Expr "Lp::Expr" and |
---|
| 89 | \ref LpBase::Constr "Lp::Constr". For example, this line |
---|
| 90 | \code |
---|
| 91 | lp.addRow(x1 - 5 <= x2); |
---|
| 92 | \endcode |
---|
| 93 | can also be written as |
---|
| 94 | \code |
---|
| 95 | Lp::Expr e1, e2; |
---|
| 96 | e1 = x1; |
---|
| 97 | e1 -= 5; |
---|
| 98 | e2 = x2; |
---|
| 99 | Lp::Constr c = e1 <= e2; |
---|
| 100 | lp.addRow(c); |
---|
| 101 | \endcode |
---|
| 102 | |
---|
| 103 | These classes make it easy to build more complex expressions and constraints, |
---|
| 104 | e.g. using loops. For example, we can sum all the variables (columns) in an |
---|
| 105 | expression using the \ref LpBase::ColIt "Lp::ColIt" iterator, which can be |
---|
| 106 | used the same as node and arc iterators for graphs. |
---|
| 107 | |
---|
| 108 | \code |
---|
| 109 | Lp::Expr sum; |
---|
| 110 | for (Lp::ColIt col(lp); col != INVALID; ++col) { |
---|
| 111 | sum += col; |
---|
[30] | 112 | } |
---|
[55] | 113 | \endcode |
---|
[30] | 114 | |
---|
[55] | 115 | After solving the problem, you can query the value of any primal expression, |
---|
| 116 | not just the individual columns and the objective function. |
---|
| 117 | |
---|
| 118 | \todo Check this example after closing ticket #326. |
---|
| 119 | |
---|
| 120 | \code |
---|
| 121 | std::cout << lp.primal(sum) << std::endl; |
---|
| 122 | \endcode |
---|
| 123 | |
---|
| 124 | Of course, working with the dual problem is also supported by the LP |
---|
| 125 | interface. \ref LpBase::Row "Lp::Row" represents the rows, i.e. the dual |
---|
| 126 | variables of the LP problem. |
---|
| 127 | |
---|
| 128 | \code |
---|
| 129 | Lp::Row r = lp.addRow(x2 >= 3); |
---|
| 130 | \endcode |
---|
| 131 | |
---|
| 132 | The dual solutions of an LP problem can be obtained using the functions |
---|
| 133 | \ref LpSolver::dualType() "dualType()" and \ref LpSolver::dual "dual()" |
---|
| 134 | (after solving the problem). |
---|
| 135 | |
---|
| 136 | \code |
---|
| 137 | std::cout << lp.dual(r) << std::endl; |
---|
| 138 | \endcode |
---|
| 139 | |
---|
| 140 | \ref LpBase::DualExpr "Lp::DualExpr" can be used to build dual expressions |
---|
| 141 | from rows and \ref LpBase::RowIt "Lp::RowIt" can be used to list the rows. |
---|
| 142 | |
---|
| 143 | \code |
---|
| 144 | Lp::DualExpr dual_sum; |
---|
| 145 | for (Lp::RowIt row(lp); row != INVALID; ++row) { |
---|
| 146 | dual_sum += row; |
---|
[30] | 147 | } |
---|
[55] | 148 | \endcode |
---|
[30] | 149 | |
---|
[55] | 150 | The LP solver interface provides several other features, which are |
---|
| 151 | documented in the classes \ref LpBase and \ref LpSolver. |
---|
| 152 | For detailed documentation, see these classes in the reference manual. |
---|
[30] | 153 | |
---|
[55] | 154 | If you would like to use a specific solver instead of the default one, |
---|
| 155 | you can use \ref GlpkLp, \ref ClpLp, \ref CplexLp etc. instead of |
---|
| 156 | the class \ref Lp. |
---|
[50] | 157 | |
---|
[55] | 158 | |
---|
| 159 | [SEC]sec_lp_mip[SEC] Mixed Integer Programming |
---|
| 160 | |
---|
| 161 | LEMON also provides a similar high-level interface for mixed integer |
---|
| 162 | programming (MIP) solvers. The default MIP solver can be used through |
---|
| 163 | the class \ref Mip, while the concrete solvers are implemented in the |
---|
| 164 | classes \ref GlpkMip, \ref CbcMip, \ref CplexMip etc. |
---|
| 165 | |
---|
| 166 | The following example demonstrates the usage of the MIP solver interface. |
---|
| 167 | The whole program can be found in \ref mip_demo.cc. |
---|
| 168 | |
---|
| 169 | \dontinclude mip_demo.cc |
---|
| 170 | \skip Create |
---|
| 171 | \until } |
---|
| 172 | \until } |
---|
| 173 | |
---|
| 174 | \todo Check this demo file after closing ticket #326. |
---|
| 175 | E.g. could we write <tt>mip.sol()</tt> instead of <tt>mip.solValue()</tt>? |
---|
| 176 | Or could we write <tt>primalValue()</tt> for \c Lp in \c lp_demo.cc? |
---|
| 177 | |
---|
| 178 | In this program, the same problem is built as in the above example, |
---|
| 179 | with the exception that the variable \c x1 is specified to be |
---|
| 180 | \c INTEGER valued. \c x2 is set to \c REAL, which is the default option. |
---|
| 181 | |
---|
| 182 | \code |
---|
| 183 | // Set the type of the columns |
---|
| 184 | mip.colType(x1, Mip::INTEGER); |
---|
| 185 | mip.colType(x2, Mip::REAL); |
---|
[30] | 186 | \endcode |
---|
| 187 | |
---|
[55] | 188 | Because of this integrality requirement, the results will be different |
---|
| 189 | from the LP solution. |
---|
| 190 | |
---|
| 191 | \code |
---|
| 192 | Objective function value: 67 |
---|
| 193 | x1 = 8 |
---|
| 194 | x2 = 9 |
---|
| 195 | \endcode |
---|
| 196 | |
---|
| 197 | The documnetation of the MIP solver interface can be found in the |
---|
| 198 | reference manual at the class \ref MipSolver. The common parts of the |
---|
| 199 | LP and MIP interfaces are docmented in their common ancestor class |
---|
| 200 | \ref LpBase. |
---|
| 201 | |
---|
| 202 | |
---|
| 203 | [SEC]sec_lp_optimization[SEC] Solving Complex Optimization Problems |
---|
| 204 | |
---|
| 205 | The LP and MIP solvers are powerful tools for solving various complex |
---|
| 206 | optimization problems, as well. |
---|
| 207 | The following example solves a maximum flow problem with linear |
---|
| 208 | programming, see the whole program in \re lp_maxflow_demo.cc. |
---|
| 209 | Several other graph optimization problems can also be expressed as |
---|
| 210 | linear programs and the interface provided in LEMON facilitates solving |
---|
| 211 | them easily (though usually not so efficiently as by a direct |
---|
| 212 | combinatorial method, if one exists). |
---|
| 213 | |
---|
| 214 | \dontinclude lp_maxflow_demo.cc |
---|
| 215 | \skip DIGRAPH_TYPEDEFS |
---|
| 216 | \until solve() |
---|
| 217 | |
---|
| 218 | \note This problem can be solved much more efficiently using common |
---|
| 219 | combinatorial optimization methods, such as the \ref Preflow |
---|
| 220 | "preflow push-relabel algorithm". |
---|
| 221 | |
---|
[30] | 222 | [TRAILER] |
---|
| 223 | */ |
---|
[32] | 224 | } |
---|