COIN-OR::LEMON - Graph Library

Changeset 48:a5457a780c34 in lemon-tutorial


Ignore:
Timestamp:
02/22/10 02:00:51 (8 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Message:

Clarify and extend the LP section

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lp.dox

    r45 r48  
    2121[PAGE]sec_lp[PAGE] Linear Programming Interface 
    2222 
    23 \todo This page is under construction. 
     23Linear programming (LP) is one of the most important general methods of 
     24operations research. Countless optimization problems can be formulated 
     25and solved using LP techniques. 
     26Therefore, developing efficient LP solvers has been of high practical 
     27interest for a long time. 
     28Nowadays various efficient LP solvers are available, including both 
     29open source and commercial software packages. 
     30Therefore, LEMON does not implement its own solver, but it features 
     31wrapper classes for several known LP packages providing a common 
     32high-level interface for all of them. 
    2433 
    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 high-level syntax. 
     34The advantage of this approach is twofold. First, our C++ interface is 
     35more comfortable than the typical native interfaces of the solvers. 
     36Second, changing the underlying solver in a certain application using 
     37LEMON's LP interface needs no effort. So, for example, one may try her 
     38idea using an open source solver, demonstrate its usability for a customer 
     39and if it works well, but the performance should be improved, then the 
     40customer may decide to purchase and use a better commercial solver. 
     41 
     42Currently, the following linear and mixed integer programming packages are 
     43supported: GLPK, Clp, Cbc, ILOG CPLEX and SoPlex. 
     44However, additional wrapper classes for new solvers can also be implemented 
     45quite easily. 
     46 
     47In this section, we will show two examples. The first one shows how simple 
     48it is to formalize and solve an LP problem in LEMON, while the second one 
     49shows how LEMON facilitates solving network optimization problems using LP 
     50solvers. 
    2951 
    3052\code 
     
    5678expressed in mathematics. 
    5779 
    58  
    5980The following example solves a maximum flow problem with linear 
    6081programming. Several other graph optimization problems can also be 
     
    6485\code 
    6586  Lp lp; 
    66   Digraph::ArcMap<Lp::Col> f(g); 
     87  ListDigraph::ArcMap<Lp::Col> f(g); 
    6788  lp.addColSet(f); 
    6889 
    6990  // Capacity constraints 
    70   for (Digraph::ArcIt a(g); a != INVALID; ++a) { 
     91  for (ListDigraph::ArcIt a(g); a != INVALID; ++a) { 
    7192    lp.colLowerBound(f[a], 0); 
    7293    lp.colUpperBound(f[a], capacity[a]); 
     
    7495 
    7596  // Flow conservation constraints 
    76   for (Digraph::NodeIt n(g); n != INVALID; ++n) { 
     97  for (ListDigraph::NodeIt n(g); n != INVALID; ++n) { 
    7798    if (n == src || n == trg) continue; 
    7899    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]; 
    81102    lp.addRow(e == 0); 
    82103  } 
     
    84105  // Objective function 
    85106  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]; 
    88109 
    89110  lp.max(); 
     
    92113\endcode 
    93114 
    94 Note that LEMON does not implement an LP solver, it just wraps various 
    95 libraries with a uniform high-level interface. 
    96 Currently, the following linear and mixed integer programming packages are 
    97 supported: GLPK, Clp, Cbc, ILOG CPLEX and SoPlex. 
    98 However, additional wrapper classes for new solvers can also be implemented 
    99 quite easily. 
    100  
    101115[TRAILER] 
    102116*/ 
Note: See TracChangeset for help on using the changeset viewer.