Changeset 48:a5457a780c34 in lemon-tutorial for lp.dox

Timestamp:

02/22/10 02:00:51 (14 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Clarify and extend the LP section

File:

• lp.dox (modified) (6 diffs)

lp.dox

@@ -21 +21 @@
 [PAGE]sec_lp[PAGE] Linear Programming Interface
 
-\todo This page is under construction.
+Linear programming (LP) is one of the most important general methods of
+operations research. Countless optimization problems can be formulated
+and solved using LP techniques.
+Therefore, developing efficient LP solvers has been of high practical
+interest for a long time.
+Nowadays various efficient LP solvers are available, including both
+open source and commercial software packages.
+Therefore, LEMON does not implement its own solver, but it features
+wrapper classes for several known LP packages providing a common
+high-level interface for all of them.
 
-Linear programming (LP) is one of the most important
-general methods of operations research and LP solvers are widely used in
-optimization software. The interface provided in LEMON makes it possible to
-specify LP problems using a high-level syntax.
+The advantage of this approach is twofold. First, our C++ interface is
+more comfortable than the typical native interfaces of the solvers.
+Second, changing the underlying solver in a certain application using
+LEMON's LP interface needs no effort. So, for example, one may try her
+idea using an open source solver, demonstrate its usability for a customer
+and if it works well, but the performance should be improved, then the
+customer may decide to purchase and use a better commercial solver.
+
+Currently, the following linear and mixed integer programming packages are
+supported: GLPK, Clp, Cbc, ILOG CPLEX and SoPlex.
+However, additional wrapper classes for new solvers can also be implemented
+quite easily.
+
+In this section, we will show two examples. The first one shows how simple
+it is to formalize and solve an LP problem in LEMON, while the second one
+shows how LEMON facilitates solving network optimization problems using LP
+solvers.
 
 \code
@@ -56 +78 @@
 expressed in mathematics.
 
-
 The following example solves a maximum flow problem with linear
 programming. Several other graph optimization problems can also be
@@ -64 +85 @@
 \code
   Lp lp;
-  Digraph::ArcMap<Lp::Col> f(g);
+  ListDigraph::ArcMap<Lp::Col> f(g);
   lp.addColSet(f);
 
   // Capacity constraints
-  for (Digraph::ArcIt a(g); a != INVALID; ++a) {
+  for (ListDigraph::ArcIt a(g); a != INVALID; ++a) {
     lp.colLowerBound(f[a], 0);
     lp.colUpperBound(f[a], capacity[a]);
@@ -74 +95 @@
 
   // Flow conservation constraints
-  for (Digraph::NodeIt n(g); n != INVALID; ++n) {
+  for (ListDigraph::NodeIt n(g); n != INVALID; ++n) {
     if (n == src || n == trg) continue;
     Lp::Expr e;
-    for (Digraph::OutArcIt a(g,n); a != INVALID; ++a) e += f[a];
-    for (Digraph::InArcIt a(g,n); a != INVALID; ++a) e -= f[a];
+    for (ListDigraph::OutArcIt a(g,n); a != INVALID; ++a) e += f[a];
+    for (ListDigraph::InArcIt a(g,n); a != INVALID; ++a) e -= f[a];
     lp.addRow(e == 0);
   }
@@ -84 +105 @@
   // Objective function
   Lp::Expr o;
-  for (Digraph::OutArcIt a(g,src); a != INVALID; ++a) o += f[a];
-  for (Digraph::InArcIt a(g,src); a != INVALID; ++a) o -= f[a];
+  for (ListDigraph::OutArcIt a(g,src); a != INVALID; ++a) o += f[a];
+  for (ListDigraph::InArcIt a(g,src); a != INVALID; ++a) o -= f[a];
 
   lp.max();
@@ -92 +113 @@
 \endcode
 
-Note that LEMON does not implement an LP solver, it just wraps various
-libraries with a uniform high-level interface.
-Currently, the following linear and mixed integer programming packages are
-supported: GLPK, Clp, Cbc, ILOG CPLEX and SoPlex.
-However, additional wrapper classes for new solvers can also be implemented
-quite easily.
-
 [TRAILER]
 */