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

 */

 }