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

 */

 }