kpeter@30: /* -*- mode: C++; indent-tabs-mode: nil; -*-
kpeter@30:  *
kpeter@30:  * This file is a part of LEMON, a generic C++ optimization library.
kpeter@30:  *
kpeter@32:  * Copyright (C) 2003-2010
kpeter@30:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@30:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@30:  *
kpeter@30:  * Permission to use, modify and distribute this software is granted
kpeter@30:  * provided that this copyright notice appears in all copies. For
kpeter@30:  * precise terms see the accompanying LICENSE file.
kpeter@30:  *
kpeter@30:  * This software is provided "AS IS" with no warranty of any kind,
kpeter@30:  * express or implied, and with no claim as to its suitability for any
kpeter@30:  * purpose.
kpeter@30:  *
kpeter@30:  */
kpeter@30: 
kpeter@30: namespace lemon {
kpeter@30: /**
kpeter@30: [PAGE]sec_lp[PAGE] Linear Programming Interface
kpeter@30: 
kpeter@30: \todo Clarify this section.
kpeter@30: 
kpeter@30: Linear programming (LP) is one of the most important
kpeter@30: general methods of operations research and LP solvers are widely used in
kpeter@30: optimization software. The interface provided in LEMON makes it possible to
kpeter@30: specify LP problems using a high-level syntax.
kpeter@30: 
kpeter@30: \code
kpeter@30:   Lp lp;
kpeter@30: 
kpeter@30:   Lp::Col x1 = lp.addCol();
kpeter@30:   Lp::Col x2 = lp.addCol();
kpeter@30: 
kpeter@30:   lp.addRow(0 <= x1 + x2 <= 100);
kpeter@30:   lp.addRow(2 * x1 <= x2 + 32);
kpeter@30: 
kpeter@30:   lp.colLowerBound(x1, 0);
kpeter@30:   lp.colUpperBound(x2, 100);
kpeter@30: 
kpeter@30:   lp.max();
kpeter@30:   lp.obj(10 * x1 + 6 * x2);
kpeter@30:   lp.solve();
kpeter@30: 
kpeter@30:   cout << "Objective function value: " << lp.primal() << endl;
kpeter@30:   cout << "x1 = " << lp.primal(x1) << endl;
kpeter@30:   cout << "x2 = " << lp.primal(x2) << endl;
kpeter@30: \endcode
kpeter@30: 
kpeter@30: \ref LpBase::Col "Lp::Col" type represents the variables in the LP problems,
kpeter@30: while \ref LpBase::Row "Lp::Row" represents the constraints. The numerical
kpeter@30: operators can be used to form expressions from columns and dual
kpeter@30: expressions from rows. Due to the suitable operator overloads,
kpeter@30: a problem can be described in C++ conveniently, directly as it is
kpeter@30: expressed in mathematics.
kpeter@30: 
kpeter@30: 
kpeter@30: The following example solves a maximum flow problem with linear
kpeter@30: programming. Several other graph optimization problems can also be
kpeter@30: expressed as linear programs and this interface helps to solve them easily
kpeter@30: (though usually not so efficiently as by a direct combinatorial method).
kpeter@30: 
kpeter@30: \code
kpeter@30:   Lp lp;
kpeter@30:   Digraph::ArcMap<Lp::Col> f(g);
kpeter@30:   lp.addColSet(f);
kpeter@30: 
kpeter@30:   // Capacity constraints
kpeter@30:   for (Digraph::ArcIt a(g); a != INVALID; ++a) {
kpeter@30:     lp.colLowerBound(f[a], 0);
kpeter@30:     lp.colUpperBound(f[a], capacity[a]);
kpeter@30:   }
kpeter@30: 
kpeter@30:   // Flow conservation constraints
kpeter@30:   for (Digraph::NodeIt n(g); n != INVALID; ++n) {
kpeter@30:     if (n == src || n == trg) continue;
kpeter@30:     Lp::Expr e;
kpeter@30:     for (Digraph::OutArcIt a(g,n); a != INVALID; ++a) e += f[a];
kpeter@30:     for (Digraph::InArcIt a(g,n); a != INVALID; ++a) e -= f[a];
kpeter@30:     lp.addRow(e == 0);
kpeter@30:   }
kpeter@30: 
kpeter@30:   // Objective function
kpeter@30:   Lp::Expr o;
kpeter@30:   for (Digraph::OutArcIt a(g,src); a != INVALID; ++a) o += f[a];
kpeter@30:   for (Digraph::InArcIt a(g,src); a != INVALID; ++a) o -= f[a];
kpeter@30: 
kpeter@30:   lp.max();
kpeter@30:   lp.obj(o);
kpeter@30:   lp.solve();
kpeter@30: \endcode
kpeter@30: 
kpeter@30: Note that LEMON does not implement an LP solver, it just wraps various
kpeter@30: libraries with a uniform high-level interface.
kpeter@30: Currently, the following linear and mixed integer programming packages are
kpeter@30: supported: GLPK, Clp, Cbc, ILOG CPLEX and SoPlex.
kpeter@30: However, additional wrapper classes for new solvers can also be implemented
kpeter@30: quite easily.
kpeter@30: 
kpeter@30: [TRAILER]
kpeter@30: */
kpeter@32: }