COIN-OR::LEMON - Graph Library

Changeset 48:a5457a780c34 in lemon-tutorial


Ignore:
Timestamp:
02/22/10 02:00:51 (9 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
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.