1.1 --- a/lp.dox	Mon Feb 22 01:59:50 2010 +0100
     1.2 +++ b/lp.dox	Mon Feb 22 02:00:51 2010 +0100
     1.3 @@ -20,12 +20,34 @@
     1.4  /**
     1.5  [PAGE]sec_lp[PAGE] Linear Programming Interface
     1.6  
     1.7 -\todo This page is under construction.
     1.8 +Linear programming (LP) is one of the most important general methods of
     1.9 +operations research. Countless optimization problems can be formulated
    1.10 +and solved using LP techniques.
    1.11 +Therefore, developing efficient LP solvers has been of high practical
    1.12 +interest for a long time.
    1.13 +Nowadays various efficient LP solvers are available, including both
    1.14 +open source and commercial software packages.
    1.15 +Therefore, LEMON does not implement its own solver, but it features
    1.16 +wrapper classes for several known LP packages providing a common
    1.17 +high-level interface for all of them.
    1.18  
    1.19 -Linear programming (LP) is one of the most important
    1.20 -general methods of operations research and LP solvers are widely used in
    1.21 -optimization software. The interface provided in LEMON makes it possible to
    1.22 -specify LP problems using a high-level syntax.
    1.23 +The advantage of this approach is twofold. First, our C++ interface is
    1.24 +more comfortable than the typical native interfaces of the solvers.
    1.25 +Second, changing the underlying solver in a certain application using
    1.26 +LEMON's LP interface needs no effort. So, for example, one may try her
    1.27 +idea using an open source solver, demonstrate its usability for a customer
    1.28 +and if it works well, but the performance should be improved, then the
    1.29 +customer may decide to purchase and use a better commercial solver.
    1.30 +
    1.31 +Currently, the following linear and mixed integer programming packages are
    1.32 +supported: GLPK, Clp, Cbc, ILOG CPLEX and SoPlex.
    1.33 +However, additional wrapper classes for new solvers can also be implemented
    1.34 +quite easily.
    1.35 +
    1.36 +In this section, we will show two examples. The first one shows how simple
    1.37 +it is to formalize and solve an LP problem in LEMON, while the second one
    1.38 +shows how LEMON facilitates solving network optimization problems using LP
    1.39 +solvers.
    1.40  
    1.41  \code
    1.42    Lp lp;
    1.43 @@ -55,7 +77,6 @@
    1.44  a problem can be described in C++ conveniently, directly as it is
    1.45  expressed in mathematics.
    1.46  
    1.47 -
    1.48  The following example solves a maximum flow problem with linear
    1.49  programming. Several other graph optimization problems can also be
    1.50  expressed as linear programs and this interface helps to solve them easily
    1.51 @@ -63,41 +84,34 @@
    1.52  
    1.53  \code
    1.54    Lp lp;
    1.55 -  Digraph::ArcMap<Lp::Col> f(g);
    1.56 +  ListDigraph::ArcMap<Lp::Col> f(g);
    1.57    lp.addColSet(f);
    1.58  
    1.59    // Capacity constraints
    1.60 -  for (Digraph::ArcIt a(g); a != INVALID; ++a) {
    1.61 +  for (ListDigraph::ArcIt a(g); a != INVALID; ++a) {
    1.62      lp.colLowerBound(f[a], 0);
    1.63      lp.colUpperBound(f[a], capacity[a]);
    1.64    }
    1.65  
    1.66    // Flow conservation constraints
    1.67 -  for (Digraph::NodeIt n(g); n != INVALID; ++n) {
    1.68 +  for (ListDigraph::NodeIt n(g); n != INVALID; ++n) {
    1.69      if (n == src || n == trg) continue;
    1.70      Lp::Expr e;
    1.71 -    for (Digraph::OutArcIt a(g,n); a != INVALID; ++a) e += f[a];
    1.72 -    for (Digraph::InArcIt a(g,n); a != INVALID; ++a) e -= f[a];
    1.73 +    for (ListDigraph::OutArcIt a(g,n); a != INVALID; ++a) e += f[a];
    1.74 +    for (ListDigraph::InArcIt a(g,n); a != INVALID; ++a) e -= f[a];
    1.75      lp.addRow(e == 0);
    1.76    }
    1.77  
    1.78    // Objective function
    1.79    Lp::Expr o;
    1.80 -  for (Digraph::OutArcIt a(g,src); a != INVALID; ++a) o += f[a];
    1.81 -  for (Digraph::InArcIt a(g,src); a != INVALID; ++a) o -= f[a];
    1.82 +  for (ListDigraph::OutArcIt a(g,src); a != INVALID; ++a) o += f[a];
    1.83 +  for (ListDigraph::InArcIt a(g,src); a != INVALID; ++a) o -= f[a];
    1.84  
    1.85    lp.max();
    1.86    lp.obj(o);
    1.87    lp.solve();
    1.88  \endcode
    1.89  
    1.90 -Note that LEMON does not implement an LP solver, it just wraps various
    1.91 -libraries with a uniform high-level interface.
    1.92 -Currently, the following linear and mixed integer programming packages are
    1.93 -supported: GLPK, Clp, Cbc, ILOG CPLEX and SoPlex.
    1.94 -However, additional wrapper classes for new solvers can also be implemented
    1.95 -quite easily.
    1.96 -
    1.97  [TRAILER]
    1.98  */
    1.99  }