Fix a type in Secion LP. Thanks for Jacint
1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2010
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
21 [PAGE]sec_lp[PAGE] Linear Programming Interface
23 Linear programming (LP) is one of the most important general methods of
24 operations research. Countless optimization problems can be formulated
25 and solved using LP techniques.
26 Therefore, developing efficient LP solvers has been of high practical
27 interest for a long time.
28 Nowadays various efficient LP solvers are available, including both
29 open source and commercial software packages.
30 Therefore, LEMON does not implement its own solver, but it features
31 wrapper classes for several known LP packages providing a common
32 high-level interface for all of them.
34 The advantage of this approach is twofold. First, our C++ interface is
35 more comfortable than the typical native interfaces of the solvers.
36 Second, changing the underlying solver in a certain application using
37 LEMON's LP interface needs no effort. So, for example, one may try her
38 idea using an open source solver, demonstrate its usability for a customer
39 and if it works well, but the performance should be improved, then the
40 customer may decide to purchase and use a better commercial solver.
42 Currently, the following linear and mixed integer programming packages are
43 supported: GLPK, Clp, Cbc, ILOG CPLEX and SoPlex.
44 However, additional wrapper classes for new solvers can also be implemented
47 [SEC]sec_lp_basics[SEC] Basic LP Features
49 The following example demonstrates how simple it is to formalize and solve
50 an LP problem in LEMON. You can find the whole program in \ref lp_demo.cc.
52 \dontinclude lp_demo.cc
57 \ref LpBase::Col "Lp::Col" type represents the columns, i.e. the (primal)
58 variables of the LP problem. The numerical operators can be used to form
59 expressions from columns, which are required for specifying rows
60 (constraints) and the objective function. Due to the suitable operator
61 overloads, a problem can be described in C++ conveniently, directly as it is
62 expressed in mathematics.
63 After specifying all the parameters of the problem, we can solve it using
64 the \ref LpSolver::solve() "solve()" function. The status of the solution
65 (namely OPTIMAL, UNBOUNDED, INFEASIBLE etc.) can be obtained using
66 \ref LpSolver::primalType() "primalType()" and the results can be
67 obtained using \ref LpSolver::primal() "primal()".
69 The above problem has an optimal solution. If you execute this example,
70 it will print out the following results.
73 Objective function value: 67.5
78 However, if you, for example, removed the lines that specify the rows,
79 you would obtain an LP problem, for which the objective function value
80 is unbounded over the feasible solutions. Thus the program would print
84 Optimal solution not found.
87 If you would like to build linear expressions or constraints in more steps,
88 then you can use the classes \ref LpBase::Expr "Lp::Expr" and
89 \ref LpBase::Constr "Lp::Constr". For example, this line
91 lp.addRow(x1 - 5 <= x2);
93 can also be written as
99 Lp::Constr c = e1 <= e2;
103 These classes make it easy to build more complex expressions and constraints,
104 e.g. using loops. For example, we can sum all the variables (columns) in an
105 expression using the \ref LpBase::ColIt "Lp::ColIt" iterator, which can be
106 used the same as node and arc iterators for graphs.
110 for (Lp::ColIt col(lp); col != INVALID; ++col) {
115 After solving the problem, you can query the value of any primal expression,
116 not just the individual columns and the objective function.
118 \todo Check this example after closing ticket #326.
121 std::cout << lp.primal(sum) << std::endl;
124 Of course, working with the dual problem is also supported by the LP
125 interface. \ref LpBase::Row "Lp::Row" represents the rows, i.e. the dual
126 variables of the LP problem.
129 Lp::Row r = lp.addRow(x2 >= 3);
132 The dual solutions of an LP problem can be obtained using the functions
133 \ref LpSolver::dualType() "dualType()" and \ref LpSolver::dual "dual()"
134 (after solving the problem).
137 std::cout << lp.dual(r) << std::endl;
140 \ref LpBase::DualExpr "Lp::DualExpr" can be used to build dual expressions
141 from rows and \ref LpBase::RowIt "Lp::RowIt" can be used to list the rows.
144 Lp::DualExpr dual_sum;
145 for (Lp::RowIt row(lp); row != INVALID; ++row) {
150 The LP solver interface provides several other features, which are
151 documented in the classes \ref LpBase and \ref LpSolver.
152 For detailed documentation, see these classes in the reference manual.
154 If you would like to use a specific solver instead of the default one,
155 you can use \ref GlpkLp, \ref ClpLp, \ref CplexLp etc. instead of
159 [SEC]sec_lp_mip[SEC] Mixed Integer Programming
161 LEMON also provides a similar high-level interface for mixed integer
162 programming (MIP) solvers. The default MIP solver can be used through
163 the class \ref Mip, while the concrete solvers are implemented in the
164 classes \ref GlpkMip, \ref CbcMip, \ref CplexMip etc.
166 The following example demonstrates the usage of the MIP solver interface.
167 The whole program can be found in \ref mip_demo.cc.
169 \dontinclude mip_demo.cc
174 \todo Check this demo file after closing ticket #326.
175 E.g. could we write <tt>mip.sol()</tt> instead of <tt>mip.solValue()</tt>?
176 Or could we write <tt>primalValue()</tt> for \c Lp in \c lp_demo.cc?
178 In this program, the same problem is built as in the above example,
179 with the exception that the variable \c x1 is specified to be
180 \c INTEGER valued. \c x2 is set to \c REAL, which is the default option.
183 // Set the type of the columns
184 mip.colType(x1, Mip::INTEGER);
185 mip.colType(x2, Mip::REAL);
188 Because of this integrality requirement, the results will be different
189 from the LP solution.
192 Objective function value: 67
197 The documentation of the MIP solver interface can be found in the
198 reference manual at the class \ref MipSolver. The common parts of the
199 LP and MIP interfaces are documented in their common ancestor class
203 [SEC]sec_lp_optimization[SEC] Solving Complex Optimization Problems
205 The LP and MIP solvers are powerful tools for solving various complex
206 optimization problems, as well.
207 The following example solves a maximum flow problem with linear
208 programming, see the whole program in \re lp_maxflow_demo.cc.
209 Several other graph optimization problems can also be expressed as
210 linear programs and the interface provided in LEMON facilitates solving
211 them easily (though usually not so efficiently as by a direct
212 combinatorial method, if one exists).
214 \dontinclude lp_maxflow_demo.cc
215 \skip DIGRAPH_TYPEDEFS
218 \note This problem can be solved much more efficiently using common
219 combinatorial optimization methods, such as the \ref Preflow
220 "preflow push-relabel algorithm".