source: lemon-tutorial/lp.dox @ 55:edb7d5759e0d

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

[SEC]sec_lp_basics[SEC] Basic LP Features

The following example demonstrates how simple it is to formalize and solve
an LP problem in LEMON. You can find the whole program in \ref lp_demo.cc.

\dontinclude lp_demo.cc
\skip Create
\until }
\until }

\ref LpBase::Col "Lp::Col" type represents the columns, i.e. the (primal)
variables of the LP problem. The numerical operators can be used to form
expressions from columns, which are required for specifying rows
(constraints) and the objective function. Due to the suitable operator
overloads, a problem can be described in C++ conveniently, directly as it is
expressed in mathematics.
After specifying all the parameters of the problem, we can solve it using
the \ref LpSolver::solve() "solve()" function. The status of the solution
(namely OPTIMAL, UNBOUNDED, INFEASIBLE etc.) can be obtained using
\ref LpSolver::primalType() "primalType()" and the results can be
obtained using \ref LpSolver::primal() "primal()".

The above problem has an optimal solution. If you execute this example,
it will print out the following results.

\code
  Objective function value: 67.5
  x1 = 7.5
  x2 = 10
\endcode

However, if you, for example, removed the lines that specify the rows,
you would obtain an LP problem, for which the objective function value
is unbounded over the feasible solutions. Thus the program would print
out this line.

\code
  Optimal solution found.
\endcode

If you would like to build linear expressions or constraints in more steps,
then you can use the classes \ref LpBase::Expr "Lp::Expr" and
\ref LpBase::Constr "Lp::Constr". For example, this line
\code
  lp.addRow(x1 - 5 <= x2);
\endcode
can also be written as
\code
  Lp::Expr e1, e2;
  e1 = x1;
  e1 -= 5;
  e2 = x2;
  Lp::Constr c = e1 <= e2;
  lp.addRow(c);
\endcode

These classes make it easy to build more complex expressions and constraints,
e.g. using loops. For example, we can sum all the variables (columns) in an
expression using the \ref LpBase::ColIt "Lp::ColIt" iterator, which can be
used the same as node and arc iterators for graphs.

\code
  Lp::Expr sum;
  for (Lp::ColIt col(lp); col != INVALID; ++col) {
    sum += col;
  }
\endcode

After solving the problem, you can query the value of any primal expression,
not just the individual columns and the objective function.

\todo Check this example after closing ticket #326.

\code
  std::cout << lp.primal(sum) << std::endl;
\endcode

Of course, working with the dual problem is also supported by the LP
interface. \ref LpBase::Row "Lp::Row" represents the rows, i.e. the dual
variables of the LP problem.

\code
  Lp::Row r = lp.addRow(x2 >= 3);
\endcode

The dual solutions of an LP problem can be obtained using the functions
\ref LpSolver::dualType() "dualType()" and \ref LpSolver::dual "dual()"
(after solving the problem).

\code
  std::cout << lp.dual(r) << std::endl;
\endcode

\ref LpBase::DualExpr "Lp::DualExpr" can be used to build dual expressions
from rows and \ref LpBase::RowIt "Lp::RowIt" can be used to list the rows.

\code
  Lp::DualExpr dual_sum;
  for (Lp::RowIt row(lp); row != INVALID; ++row) {
    dual_sum += row;
  }
\endcode

The LP solver interface provides several other features, which are
documented in the classes \ref LpBase and \ref LpSolver.
For detailed documentation, see these classes in the reference manual.

If you would like to use a specific solver instead of the default one,
you can use \ref GlpkLp, \ref ClpLp, \ref CplexLp etc. instead of
the class \ref Lp.


[SEC]sec_lp_mip[SEC] Mixed Integer Programming

LEMON also provides a similar high-level interface for mixed integer
programming (MIP) solvers. The default MIP solver can be used through
the class \ref Mip, while the concrete solvers are implemented in the
classes \ref GlpkMip, \ref CbcMip, \ref CplexMip etc.

The following example demonstrates the usage of the MIP solver interface.
The whole program can be found in \ref mip_demo.cc.

\dontinclude mip_demo.cc
\skip Create
\until }
\until }

\todo Check this demo file after closing ticket #326.
E.g. could we write <tt>mip.sol()</tt> instead of <tt>mip.solValue()</tt>?
Or could we write <tt>primalValue()</tt> for \c Lp in \c lp_demo.cc?

In this program, the same problem is built as in the above example,
with the exception that the variable \c x1 is specified to be
\c INTEGER valued. \c x2 is set to \c REAL, which is the default option.

\code
  // Set the type of the columns
  mip.colType(x1, Mip::INTEGER);
  mip.colType(x2, Mip::REAL);
\endcode

Because of this integrality requirement, the results will be different
from the LP solution.

\code
  Objective function value: 67
  x1 = 8
  x2 = 9
\endcode

The documnetation of the MIP solver interface can be found in the
reference manual at the class \ref MipSolver. The common parts of the
LP and MIP interfaces are docmented in their common ancestor class
\ref LpBase.


[SEC]sec_lp_optimization[SEC] Solving Complex Optimization Problems

The LP and MIP solvers are powerful tools for solving various complex
optimization problems, as well.
The following example solves a maximum flow problem with linear
programming, see the whole program in \re lp_maxflow_demo.cc.
Several other graph optimization problems can also be expressed as
linear programs and the interface provided in LEMON facilitates solving
them easily (though usually not so efficiently as by a direct
combinatorial method, if one exists). 

\dontinclude lp_maxflow_demo.cc
\skip DIGRAPH_TYPEDEFS
\until solve()

\note This problem can be solved much more efficiently using common
combinatorial optimization methods, such as the \ref Preflow
"preflow push-relabel algorithm".

[TRAILER]
*/
}