source: lemon-tutorial/lp.dox @ 42:6df2bf124af4

/* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library.
 *
 * Copyright (C) 2003-2010
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

namespace lemon {
/**
[PAGE]sec_lp[PAGE] Linear Programming Interface

\todo Clarify this section.

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.

\code
  Lp lp;

  Lp::Col x1 = lp.addCol();
  Lp::Col x2 = lp.addCol();

  lp.addRow(0 <= x1 + x2 <= 100);
  lp.addRow(2 * x1 <= x2 + 32);

  lp.colLowerBound(x1, 0);
  lp.colUpperBound(x2, 100);

  lp.max();
  lp.obj(10 * x1 + 6 * x2);
  lp.solve();

  cout << "Objective function value: " << lp.primal() << endl;
  cout << "x1 = " << lp.primal(x1) << endl;
  cout << "x2 = " << lp.primal(x2) << endl;
\endcode

\ref LpBase::Col "Lp::Col" type represents the variables in the LP problems,
while \ref LpBase::Row "Lp::Row" represents the constraints. The numerical
operators can be used to form expressions from columns and dual
expressions from rows. Due to the suitable operator overloads,
a problem can be described in C++ conveniently, directly as it is
expressed in mathematics.


The following example solves a maximum flow problem with linear
programming. Several other graph optimization problems can also be
expressed as linear programs and this interface helps to solve them easily
(though usually not so efficiently as by a direct combinatorial method).

\code
  Lp lp;
  Digraph::ArcMap<Lp::Col> f(g);
  lp.addColSet(f);

  // Capacity constraints
  for (Digraph::ArcIt a(g); a != INVALID; ++a) {
    lp.colLowerBound(f[a], 0);
    lp.colUpperBound(f[a], capacity[a]);
  }

  // Flow conservation constraints
  for (Digraph::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];
    lp.addRow(e == 0);
  }

  // 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];

  lp.max();
  lp.obj(o);
  lp.solve();
\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]
*/
}