1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/lp.dox	Mon Feb 15 01:24:45 2010 +0100
     1.3 @@ -0,0 +1,103 @@
     1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     1.5 + *
     1.6 + * This file is a part of LEMON, a generic C++ optimization library.
     1.7 + *
     1.8 + * Copyright (C) 2003-2009
     1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11 + *
    1.12 + * Permission to use, modify and distribute this software is granted
    1.13 + * provided that this copyright notice appears in all copies. For
    1.14 + * precise terms see the accompanying LICENSE file.
    1.15 + *
    1.16 + * This software is provided "AS IS" with no warranty of any kind,
    1.17 + * express or implied, and with no claim as to its suitability for any
    1.18 + * purpose.
    1.19 + *
    1.20 + */
    1.21 +
    1.22 +namespace lemon {
    1.23 +/**
    1.24 +[PAGE]sec_lp[PAGE] Linear Programming Interface
    1.25 +
    1.26 +\todo Clarify this section.
    1.27 +
    1.28 +Linear programming (LP) is one of the most important
    1.29 +general methods of operations research and LP solvers are widely used in
    1.30 +optimization software. The interface provided in LEMON makes it possible to
    1.31 +specify LP problems using a high-level syntax.
    1.32 +
    1.33 +\code
    1.34 +  Lp lp;
    1.35 +
    1.36 +  Lp::Col x1 = lp.addCol();
    1.37 +  Lp::Col x2 = lp.addCol();
    1.38 +
    1.39 +  lp.addRow(0 <= x1 + x2 <= 100);
    1.40 +  lp.addRow(2 * x1 <= x2 + 32);
    1.41 +
    1.42 +  lp.colLowerBound(x1, 0);
    1.43 +  lp.colUpperBound(x2, 100);
    1.44 +
    1.45 +  lp.max();
    1.46 +  lp.obj(10 * x1 + 6 * x2);
    1.47 +  lp.solve();
    1.48 +
    1.49 +  cout << "Objective function value: " << lp.primal() << endl;
    1.50 +  cout << "x1 = " << lp.primal(x1) << endl;
    1.51 +  cout << "x2 = " << lp.primal(x2) << endl;
    1.52 +\endcode
    1.53 +
    1.54 +\ref LpBase::Col "Lp::Col" type represents the variables in the LP problems,
    1.55 +while \ref LpBase::Row "Lp::Row" represents the constraints. The numerical
    1.56 +operators can be used to form expressions from columns and dual
    1.57 +expressions from rows. Due to the suitable operator overloads,
    1.58 +a problem can be described in C++ conveniently, directly as it is
    1.59 +expressed in mathematics.
    1.60 +
    1.61 +
    1.62 +The following example solves a maximum flow problem with linear
    1.63 +programming. Several other graph optimization problems can also be
    1.64 +expressed as linear programs and this interface helps to solve them easily
    1.65 +(though usually not so efficiently as by a direct combinatorial method).
    1.66 +
    1.67 +\code
    1.68 +  Lp lp;
    1.69 +  Digraph::ArcMap<Lp::Col> f(g);
    1.70 +  lp.addColSet(f);
    1.71 +
    1.72 +  // Capacity constraints
    1.73 +  for (Digraph::ArcIt a(g); a != INVALID; ++a) {
    1.74 +    lp.colLowerBound(f[a], 0);
    1.75 +    lp.colUpperBound(f[a], capacity[a]);
    1.76 +  }
    1.77 +
    1.78 +  // Flow conservation constraints
    1.79 +  for (Digraph::NodeIt n(g); n != INVALID; ++n) {
    1.80 +    if (n == src || n == trg) continue;
    1.81 +    Lp::Expr e;
    1.82 +    for (Digraph::OutArcIt a(g,n); a != INVALID; ++a) e += f[a];
    1.83 +    for (Digraph::InArcIt a(g,n); a != INVALID; ++a) e -= f[a];
    1.84 +    lp.addRow(e == 0);
    1.85 +  }
    1.86 +
    1.87 +  // Objective function
    1.88 +  Lp::Expr o;
    1.89 +  for (Digraph::OutArcIt a(g,src); a != INVALID; ++a) o += f[a];
    1.90 +  for (Digraph::InArcIt a(g,src); a != INVALID; ++a) o -= f[a];
    1.91 +
    1.92 +  lp.max();
    1.93 +  lp.obj(o);
    1.94 +  lp.solve();
    1.95 +\endcode
    1.96 +
    1.97 +Note that LEMON does not implement an LP solver, it just wraps various
    1.98 +libraries with a uniform high-level interface.
    1.99 +Currently, the following linear and mixed integer programming packages are
   1.100 +supported: GLPK, Clp, Cbc, ILOG CPLEX and SoPlex.
   1.101 +However, additional wrapper classes for new solvers can also be implemented
   1.102 +quite easily.
   1.103 +
   1.104 +[TRAILER]
   1.105 +*/
   1.106 +}
   1.107 \ No newline at end of file

     2.1 --- a/toc.txt	Mon Feb 15 01:18:18 2010 +0100
     2.2 +++ b/toc.txt	Mon Feb 15 01:24:45 2010 +0100
     2.3 @@ -17,8 +17,9 @@
     2.4  ** sec_undir_graphs
     2.5  ** sec_special_graphs
     2.6  * sec_graph_adaptors
     2.7 +* sec_lp
     2.8 +*_sec_lgf
     2.9  *_sec_tools
    2.10 -**_sec_lgf
    2.11  **_sec_time_count
    2.12  **_sec_random
    2.13  **_sec_graph_to_eps