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

*/

}