source: lemon-tutorial/lp.dox @ 53:0f695eac7e07

/* -*- 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

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.

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
  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();

  std::cout << "Objective function value: " << lp.primal() << std::endl;
  std::cout << "x1 = " << lp.primal(x1) << std::endl;
  std::cout << "x2 = " << lp.primal(x2) << std::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;
  ListDigraph::ArcMap<Lp::Col> f(g);
  lp.addColSet(f);

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

  // Flow conservation constraints
  for (ListDigraph::NodeIt n(g); n != INVALID; ++n) {
    if (n == src || n == trg) continue;
    Lp::Expr e;
    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);
  }

  // Objective function
  Lp::Expr o;
  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();
  lp.obj(o);
  lp.solve();

  std::cout << "Max flow value: " << lp.primal() << std::endl;
\endcode

[TRAILER]
*/
}