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@48: Linear programming (LP) is one of the most important general methods of
kpeter@48: operations research. Countless optimization problems can be formulated
kpeter@48: and solved using LP techniques.
kpeter@48: Therefore, developing efficient LP solvers has been of high practical
kpeter@48: interest for a long time.
kpeter@48: Nowadays various efficient LP solvers are available, including both
kpeter@48: open source and commercial software packages.
kpeter@48: Therefore, LEMON does not implement its own solver, but it features
kpeter@48: wrapper classes for several known LP packages providing a common
kpeter@48: high-level interface for all of them.
kpeter@30: 
kpeter@48: The advantage of this approach is twofold. First, our C++ interface is
kpeter@48: more comfortable than the typical native interfaces of the solvers.
kpeter@48: Second, changing the underlying solver in a certain application using
kpeter@48: LEMON's LP interface needs no effort. So, for example, one may try her
kpeter@48: idea using an open source solver, demonstrate its usability for a customer
kpeter@48: and if it works well, but the performance should be improved, then the
kpeter@48: customer may decide to purchase and use a better commercial solver.
kpeter@48: 
kpeter@48: Currently, the following linear and mixed integer programming packages are
kpeter@48: supported: GLPK, Clp, Cbc, ILOG CPLEX and SoPlex.
kpeter@48: However, additional wrapper classes for new solvers can also be implemented
kpeter@48: quite easily.
kpeter@48: 
kpeter@55: [SEC]sec_lp_basics[SEC] Basic LP Features
kpeter@55: 
kpeter@55: The following example demonstrates how simple it is to formalize and solve
kpeter@55: an LP problem in LEMON. You can find the whole program in \ref lp_demo.cc.
kpeter@55: 
kpeter@55: \dontinclude lp_demo.cc
kpeter@55: \skip Create
kpeter@55: \until }
kpeter@55: \until }
kpeter@55: 
kpeter@55: \ref LpBase::Col "Lp::Col" type represents the columns, i.e. the (primal)
kpeter@55: variables of the LP problem. The numerical operators can be used to form
kpeter@55: expressions from columns, which are required for specifying rows
kpeter@55: (constraints) and the objective function. Due to the suitable operator
kpeter@55: overloads, a problem can be described in C++ conveniently, directly as it is
kpeter@55: expressed in mathematics.
kpeter@55: After specifying all the parameters of the problem, we can solve it using
kpeter@55: the \ref LpSolver::solve() "solve()" function. The status of the solution
kpeter@55: (namely OPTIMAL, UNBOUNDED, INFEASIBLE etc.) can be obtained using
kpeter@55: \ref LpSolver::primalType() "primalType()" and the results can be
kpeter@55: obtained using \ref LpSolver::primal() "primal()".
kpeter@55: 
kpeter@55: The above problem has an optimal solution. If you execute this example,
kpeter@55: it will print out the following results.
kpeter@30: 
kpeter@30: \code
kpeter@55:   Objective function value: 67.5
kpeter@55:   x1 = 7.5
kpeter@55:   x2 = 10
kpeter@30: \endcode
kpeter@30: 
kpeter@55: However, if you, for example, removed the lines that specify the rows,
kpeter@55: you would obtain an LP problem, for which the objective function value
kpeter@55: is unbounded over the feasible solutions. Thus the program would print
kpeter@55: out this line.
kpeter@30: 
kpeter@30: \code
kpeter@55:   Optimal solution found.
kpeter@55: \endcode
kpeter@30: 
kpeter@55: If you would like to build linear expressions or constraints in more steps,
kpeter@55: then you can use the classes \ref LpBase::Expr "Lp::Expr" and
kpeter@55: \ref LpBase::Constr "Lp::Constr". For example, this line
kpeter@55: \code
kpeter@55:   lp.addRow(x1 - 5 <= x2);
kpeter@55: \endcode
kpeter@55: can also be written as
kpeter@55: \code
kpeter@55:   Lp::Expr e1, e2;
kpeter@55:   e1 = x1;
kpeter@55:   e1 -= 5;
kpeter@55:   e2 = x2;
kpeter@55:   Lp::Constr c = e1 <= e2;
kpeter@55:   lp.addRow(c);
kpeter@55: \endcode
kpeter@55: 
kpeter@55: These classes make it easy to build more complex expressions and constraints,
kpeter@55: e.g. using loops. For example, we can sum all the variables (columns) in an
kpeter@55: expression using the \ref LpBase::ColIt "Lp::ColIt" iterator, which can be
kpeter@55: used the same as node and arc iterators for graphs.
kpeter@55: 
kpeter@55: \code
kpeter@55:   Lp::Expr sum;
kpeter@55:   for (Lp::ColIt col(lp); col != INVALID; ++col) {
kpeter@55:     sum += col;
kpeter@30:   }
kpeter@55: \endcode
kpeter@30: 
kpeter@55: After solving the problem, you can query the value of any primal expression,
kpeter@55: not just the individual columns and the objective function.
kpeter@55: 
kpeter@55: \todo Check this example after closing ticket #326.
kpeter@55: 
kpeter@55: \code
kpeter@55:   std::cout << lp.primal(sum) << std::endl;
kpeter@55: \endcode
kpeter@55: 
kpeter@55: Of course, working with the dual problem is also supported by the LP
kpeter@55: interface. \ref LpBase::Row "Lp::Row" represents the rows, i.e. the dual
kpeter@55: variables of the LP problem.
kpeter@55: 
kpeter@55: \code
kpeter@55:   Lp::Row r = lp.addRow(x2 >= 3);
kpeter@55: \endcode
kpeter@55: 
kpeter@55: The dual solutions of an LP problem can be obtained using the functions
kpeter@55: \ref LpSolver::dualType() "dualType()" and \ref LpSolver::dual "dual()"
kpeter@55: (after solving the problem).
kpeter@55: 
kpeter@55: \code
kpeter@55:   std::cout << lp.dual(r) << std::endl;
kpeter@55: \endcode
kpeter@55: 
kpeter@55: \ref LpBase::DualExpr "Lp::DualExpr" can be used to build dual expressions
kpeter@55: from rows and \ref LpBase::RowIt "Lp::RowIt" can be used to list the rows.
kpeter@55: 
kpeter@55: \code
kpeter@55:   Lp::DualExpr dual_sum;
kpeter@55:   for (Lp::RowIt row(lp); row != INVALID; ++row) {
kpeter@55:     dual_sum += row;
kpeter@30:   }
kpeter@55: \endcode
kpeter@30: 
kpeter@55: The LP solver interface provides several other features, which are
kpeter@55: documented in the classes \ref LpBase and \ref LpSolver.
kpeter@55: For detailed documentation, see these classes in the reference manual.
kpeter@30: 
kpeter@55: If you would like to use a specific solver instead of the default one,
kpeter@55: you can use \ref GlpkLp, \ref ClpLp, \ref CplexLp etc. instead of
kpeter@55: the class \ref Lp.
kpeter@50: 
kpeter@55: 
kpeter@55: [SEC]sec_lp_mip[SEC] Mixed Integer Programming
kpeter@55: 
kpeter@55: LEMON also provides a similar high-level interface for mixed integer
kpeter@55: programming (MIP) solvers. The default MIP solver can be used through
kpeter@55: the class \ref Mip, while the concrete solvers are implemented in the
kpeter@55: classes \ref GlpkMip, \ref CbcMip, \ref CplexMip etc.
kpeter@55: 
kpeter@55: The following example demonstrates the usage of the MIP solver interface.
kpeter@55: The whole program can be found in \ref mip_demo.cc.
kpeter@55: 
kpeter@55: \dontinclude mip_demo.cc
kpeter@55: \skip Create
kpeter@55: \until }
kpeter@55: \until }
kpeter@55: 
kpeter@55: \todo Check this demo file after closing ticket #326.
kpeter@55: E.g. could we write <tt>mip.sol()</tt> instead of <tt>mip.solValue()</tt>?
kpeter@55: Or could we write <tt>primalValue()</tt> for \c Lp in \c lp_demo.cc?
kpeter@55: 
kpeter@55: In this program, the same problem is built as in the above example,
kpeter@55: with the exception that the variable \c x1 is specified to be
kpeter@55: \c INTEGER valued. \c x2 is set to \c REAL, which is the default option.
kpeter@55: 
kpeter@55: \code
kpeter@55:   // Set the type of the columns
kpeter@55:   mip.colType(x1, Mip::INTEGER);
kpeter@55:   mip.colType(x2, Mip::REAL);
kpeter@30: \endcode
kpeter@30: 
kpeter@55: Because of this integrality requirement, the results will be different
kpeter@55: from the LP solution.
kpeter@55: 
kpeter@55: \code
kpeter@55:   Objective function value: 67
kpeter@55:   x1 = 8
kpeter@55:   x2 = 9
kpeter@55: \endcode
kpeter@55: 
kpeter@57: The documentation of the MIP solver interface can be found in the
kpeter@55: reference manual at the class \ref MipSolver. The common parts of the
kpeter@57: LP and MIP interfaces are documented in their common ancestor class
kpeter@55: \ref LpBase.
kpeter@55: 
kpeter@55: 
kpeter@55: [SEC]sec_lp_optimization[SEC] Solving Complex Optimization Problems
kpeter@55: 
kpeter@55: The LP and MIP solvers are powerful tools for solving various complex
kpeter@55: optimization problems, as well.
kpeter@55: The following example solves a maximum flow problem with linear
kpeter@55: programming, see the whole program in \re lp_maxflow_demo.cc.
kpeter@55: Several other graph optimization problems can also be expressed as
kpeter@55: linear programs and the interface provided in LEMON facilitates solving
kpeter@55: them easily (though usually not so efficiently as by a direct
kpeter@55: combinatorial method, if one exists). 
kpeter@55: 
kpeter@55: \dontinclude lp_maxflow_demo.cc
kpeter@55: \skip DIGRAPH_TYPEDEFS
kpeter@55: \until solve()
kpeter@55: 
kpeter@55: \note This problem can be solved much more efficiently using common
kpeter@55: combinatorial optimization methods, such as the \ref Preflow
kpeter@55: "preflow push-relabel algorithm".
kpeter@55: 
kpeter@30: [TRAILER]
kpeter@30: */
kpeter@32: }