Changeset 1517:b303c1741c9a in lemon0.x for doc/quicktour.dox
 Timestamp:
 06/27/05 17:22:34 (16 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2002
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

doc/quicktour.dox
r1514 r1517 142 142 Ide Zsuzska fog irni! 143 143 144 <li>Many problems in network optimization can be formalized by means of a 145 linear programming problem (LP problem, for short). In our library we decided 146 not to write an LP solver, since such packages are available in the commercial 147 world just as well as in the open source world, and it is also a difficult 148 task to compete these. Instead we decided to develop an interface that makes 149 it easier to use these solvers together with LEMON. So far we have an 144 <li>Many problems in network optimization can be formalized by means 145 of a linear programming problem (LP problem, for short). In our 146 library we decided not to write an LP solver, since such packages are 147 available in the commercial world just as well as in the open source 148 world, and it is also a difficult task to compete these. Instead we 149 decided to develop an interface that makes it easier to use these 150 solvers together with LEMON. The advantage of this approach is 151 twofold. Firstly our C++ interface is more comfortable than the 152 solvers' native interface. Secondly, changing the underlying solver in 153 a certain software using LEMON's LP interface needs zero effort. So, 154 for example, one may try his idea using a free solver, demonstrate its 155 usability for a customer and if it works well, but the performance 156 should be improved, then one may decide to purchase and use a better 157 commercial solver. 158 159 So far we have an 150 160 interface for the commercial LP solver software \b CLPLEX (developed by ILOG) 151 161 and for the open source solver \b GLPK (a shorthand for Gnu Linear Programming 152 Toolkit). 162 Toolkit). 153 163 154 164 We will show two examples, the first one shows how simple it is to formalize … … 158 168 <ol> 159 169 <li>The following code shows how to solve an LP problem using the LEMON lp 160 interface. 170 interface. The code together with the comments is selfexplanatory. 161 171 162 172 \code … … 205 215 See the whole code in \ref lp_demo.cc. 206 216 207 <li>The second example shows how easy it is to formalize a network 208 optimization problem as an LP problem using the LEMON LP interface. 217 <li>The second example shows how easy it is to formalize a maxflow 218 problem as an LP problem using the LEMON LP interface: we are looking 219 for a real valued function defined on the edges of the digraph 220 satisfying the nonnegativity, the capacity constraints and the 221 flowconservation constraints and giving the largest flow value 222 between to designated nodes. 223 224 In the following code we suppose that we already have the graph \c g, 225 the capacity map \c cap, the source node \c s and the target node \c t 226 in the memory. We will also omit the typedefs. 227 228 \code 229 //Define a map on the edges for the variables of the LP problem 230 typename G::template EdgeMap<LpDefault::Col> x(g); 231 lp.addColSet(x); 232 233 //Nonnegativity and capacity constraints 234 for(EdgeIt e(g);e!=INVALID;++e) { 235 lp.colUpperBound(x[e],cap[e]); 236 lp.colLowerBound(x[e],0); 237 } 238 239 240 //Flow conservation constraints for the nodes (except for 's' and 't') 241 for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) { 242 LpDefault::Expr ex; 243 for(InEdgeIt e(g,n);e!=INVALID;++e) ex+=x[e]; 244 for(OutEdgeIt e(g,n);e!=INVALID;++e) ex=x[e]; 245 lp.addRow(ex==0); 246 } 247 248 //Objective function: the flow value entering 't' 249 { 250 LpDefault::Expr ex; 251 for(InEdgeIt e(g,t);e!=INVALID;++e) ex+=x[e]; 252 for(OutEdgeIt e(g,t);e!=INVALID;++e) ex=x[e]; 253 lp.setObj(ex); 254 } 255 256 //Maximization 257 lp.max(); 258 259 //Solve with the underlying solver 260 lp.solve(); 261 262 \endcode 263 264 The complete program can be found in file \ref lp_maxflow_demo.cc. After compiling run it in the form: 265 266 <tt>./lp_maxflow_demo < ?????????.lgf</tt> 267 268 where ?????????.lgf is a file in the lemon format containing a maxflow instance (designated "source", "target" nodes and "capacity" map). 269 270 271 See the whole code in \ref lp_demo.cc. 272 209 273 210 274 </ol>
Note: See TracChangeset
for help on using the changeset viewer.