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

*/

}