Changeset 48:a5457a780c34 in lemontutorial for lp.dox
Legend:
 Unmodified
 Added
 Removed

lp.dox
r45 r48 21 21 [PAGE]sec_lp[PAGE] Linear Programming Interface 22 22 23 \todo This page is under construction. 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 highlevel interface for all of them. 24 33 25 Linear programming (LP) is one of the most important 26 general methods of operations research and LP solvers are widely used in 27 optimization software. The interface provided in LEMON makes it possible to 28 specify LP problems using a highlevel syntax. 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 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. 29 51 30 52 \code … … 56 78 expressed in mathematics. 57 79 58 59 80 The following example solves a maximum flow problem with linear 60 81 programming. Several other graph optimization problems can also be … … 64 85 \code 65 86 Lp lp; 66 Digraph::ArcMap<Lp::Col> f(g);87 ListDigraph::ArcMap<Lp::Col> f(g); 67 88 lp.addColSet(f); 68 89 69 90 // Capacity constraints 70 for ( Digraph::ArcIt a(g); a != INVALID; ++a) {91 for (ListDigraph::ArcIt a(g); a != INVALID; ++a) { 71 92 lp.colLowerBound(f[a], 0); 72 93 lp.colUpperBound(f[a], capacity[a]); … … 74 95 75 96 // Flow conservation constraints 76 for ( Digraph::NodeIt n(g); n != INVALID; ++n) {97 for (ListDigraph::NodeIt n(g); n != INVALID; ++n) { 77 98 if (n == src  n == trg) continue; 78 99 Lp::Expr e; 79 for ( Digraph::OutArcIt a(g,n); a != INVALID; ++a) e += f[a];80 for ( Digraph::InArcIt a(g,n); a != INVALID; ++a) e = f[a];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]; 81 102 lp.addRow(e == 0); 82 103 } … … 84 105 // Objective function 85 106 Lp::Expr o; 86 for ( Digraph::OutArcIt a(g,src); a != INVALID; ++a) o += f[a];87 for ( Digraph::InArcIt a(g,src); a != INVALID; ++a) o = f[a];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]; 88 109 89 110 lp.max(); … … 92 113 \endcode 93 114 94 Note that LEMON does not implement an LP solver, it just wraps various95 libraries with a uniform highlevel interface.96 Currently, the following linear and mixed integer programming packages are97 supported: GLPK, Clp, Cbc, ILOG CPLEX and SoPlex.98 However, additional wrapper classes for new solvers can also be implemented99 quite easily.100 101 115 [TRAILER] 102 116 */
Note: See TracChangeset
for help on using the changeset viewer.