Changeset 55:edb7d5759e0d in lemontutorial
Legend:
 Unmodified
 Added
 Removed

lp.dox
r50 r55 45 45 quite easily. 46 46 47 In this section, we will show two examples. The first one shows how simple 48 it is to formalize and solve an LP problem in LEMON, while the second one 49 shows how LEMON facilitates solving network optimization problems using LP 50 solvers. 51 52 \code 53 Lp lp; 54 55 Lp::Col x1 = lp.addCol(); 56 Lp::Col x2 = lp.addCol(); 57 58 lp.addRow(0 <= x1 + x2 <= 100); 59 lp.addRow(2 * x1 <= x2 + 32); 60 61 lp.colLowerBound(x1, 0); 62 lp.colUpperBound(x2, 100); 63 64 lp.max(); 65 lp.obj(10 * x1 + 6 * x2); 66 lp.solve(); 67 68 std::cout << "Objective function value: " << lp.primal() << std::endl; 69 std::cout << "x1 = " << lp.primal(x1) << std::endl; 70 std::cout << "x2 = " << lp.primal(x2) << std::endl; 71 \endcode 72 73 \ref LpBase::Col "Lp::Col" type represents the variables in the LP problems, 74 while \ref LpBase::Row "Lp::Row" represents the constraints. The numerical 75 operators can be used to form expressions from columns and dual 76 expressions from rows. Due to the suitable operator overloads, 77 a problem can be described in C++ conveniently, directly as it is 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 78 62 expressed in mathematics. 79 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. 71 72 \code 73 Objective function value: 67.5 74 x1 = 7.5 75 x2 = 10 76 \endcode 77 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. 82 83 \code 84 Optimal solution found. 85 \endcode 86 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; 112 } 113 \endcode 114 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; 147 } 148 \endcode 149 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. 153 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. 157 158 159 [SEC]sec_lp_mip[SEC] Mixed Integer Programming 160 161 LEMON also provides a similar highlevel 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); 186 \endcode 187 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. 80 207 The following example solves a maximum flow problem with linear 81 programming. Several other graph optimization problems can also be 82 expressed as linear programs and this interface helps to solve them easily 83 (though usually not so efficiently as by a direct combinatorial method). 84 85 \code 86 Lp lp; 87 ListDigraph::ArcMap<Lp::Col> f(g); 88 lp.addColSet(f); 89 90 // Capacity constraints 91 for (ListDigraph::ArcIt a(g); a != INVALID; ++a) { 92 lp.colLowerBound(f[a], 0); 93 lp.colUpperBound(f[a], capacity[a]); 94 } 95 96 // Flow conservation constraints 97 for (ListDigraph::NodeIt n(g); n != INVALID; ++n) { 98 if (n == src  n == trg) continue; 99 Lp::Expr e; 100 for (ListDigraph::OutArcIt a(g,n); a != INVALID; ++a) e += f[a]; 101 for (ListDigraph::InArcIt a(g,n); a != INVALID; ++a) e = f[a]; 102 lp.addRow(e == 0); 103 } 104 105 // Objective function 106 Lp::Expr o; 107 for (ListDigraph::OutArcIt a(g,src); a != INVALID; ++a) o += f[a]; 108 for (ListDigraph::InArcIt a(g,src); a != INVALID; ++a) o = f[a]; 109 110 lp.max(); 111 lp.obj(o); 112 lp.solve(); 113 114 std::cout << "Max flow value: " << lp.primal() << std::endl; 115 \endcode 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 pushrelabel algorithm". 116 221 117 222 [TRAILER] 
toc.txt
r46 r55 34 34 ** sec_other_adaptors 35 35 * sec_lp 36 ** sec_lp_basics 37 ** sec_lp_mip 38 ** sec_lp_optimization 36 39 * sec_lgf 37 40 * sec_tools
Note: See TracChangeset
for help on using the changeset viewer.