COIN-OR::LEMON - Graph Library

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

Last change on this file since 55:edb7d5759e0d was 55:edb7d5759e0d, checked in by Peter Kovacs <kpeter@…>, 14 years ago

Greatly extend LP section

File size: 7.5 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2010
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
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.
12 *
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
15 * purpose.
16 *
17 */
18
19namespace lemon {
20/**
21[PAGE]sec_lp[PAGE] Linear Programming Interface
22
23Linear programming (LP) is one of the most important general methods of
24operations research. Countless optimization problems can be formulated
25and solved using LP techniques.
26Therefore, developing efficient LP solvers has been of high practical
27interest for a long time.
28Nowadays various efficient LP solvers are available, including both
29open source and commercial software packages.
30Therefore, LEMON does not implement its own solver, but it features
31wrapper classes for several known LP packages providing a common
32high-level interface for all of them.
33
34The advantage of this approach is twofold. First, our C++ interface is
35more comfortable than the typical native interfaces of the solvers.
36Second, changing the underlying solver in a certain application using
37LEMON's LP interface needs no effort. So, for example, one may try her
38idea using an open source solver, demonstrate its usability for a customer
39and if it works well, but the performance should be improved, then the
40customer may decide to purchase and use a better commercial solver.
41
42Currently, the following linear and mixed integer programming packages are
43supported: GLPK, Clp, Cbc, ILOG CPLEX and SoPlex.
44However, additional wrapper classes for new solvers can also be implemented
45quite easily.
46
47[SEC]sec_lp_basics[SEC] Basic LP Features
48
49The following example demonstrates how simple it is to formalize and solve
50an LP problem in LEMON. You can find the whole program in \ref lp_demo.cc.
51
52\dontinclude lp_demo.cc
53\skip Create
54\until }
55\until }
56
57\ref LpBase::Col "Lp::Col" type represents the columns, i.e. the (primal)
58variables of the LP problem. The numerical operators can be used to form
59expressions from columns, which are required for specifying rows
60(constraints) and the objective function. Due to the suitable operator
61overloads, a problem can be described in C++ conveniently, directly as it is
62expressed in mathematics.
63After specifying all the parameters of the problem, we can solve it using
64the \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
67obtained using \ref LpSolver::primal() "primal()".
68
69The above problem has an optimal solution. If you execute this example,
70it will print out the following results.
71
72\code
73  Objective function value: 67.5
74  x1 = 7.5
75  x2 = 10
76\endcode
77
78However, if you, for example, removed the lines that specify the rows,
79you would obtain an LP problem, for which the objective function value
80is unbounded over the feasible solutions. Thus the program would print
81out this line.
82
83\code
84  Optimal solution found.
85\endcode
86
87If you would like to build linear expressions or constraints in more steps,
88then you can use the classes \ref LpBase::Expr "Lp::Expr" and
89\ref LpBase::Constr "Lp::Constr". For example, this line
90\code
91  lp.addRow(x1 - 5 <= x2);
92\endcode
93can also be written as
94\code
95  Lp::Expr e1, e2;
96  e1 = x1;
97  e1 -= 5;
98  e2 = x2;
99  Lp::Constr c = e1 <= e2;
100  lp.addRow(c);
101\endcode
102
103These classes make it easy to build more complex expressions and constraints,
104e.g. using loops. For example, we can sum all the variables (columns) in an
105expression using the \ref LpBase::ColIt "Lp::ColIt" iterator, which can be
106used the same as node and arc iterators for graphs.
107
108\code
109  Lp::Expr sum;
110  for (Lp::ColIt col(lp); col != INVALID; ++col) {
111    sum += col;
112  }
113\endcode
114
115After solving the problem, you can query the value of any primal expression,
116not just the individual columns and the objective function.
117
118\todo Check this example after closing ticket #326.
119
120\code
121  std::cout << lp.primal(sum) << std::endl;
122\endcode
123
124Of course, working with the dual problem is also supported by the LP
125interface. \ref LpBase::Row "Lp::Row" represents the rows, i.e. the dual
126variables of the LP problem.
127
128\code
129  Lp::Row r = lp.addRow(x2 >= 3);
130\endcode
131
132The 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).
135
136\code
137  std::cout << lp.dual(r) << std::endl;
138\endcode
139
140\ref LpBase::DualExpr "Lp::DualExpr" can be used to build dual expressions
141from rows and \ref LpBase::RowIt "Lp::RowIt" can be used to list the rows.
142
143\code
144  Lp::DualExpr dual_sum;
145  for (Lp::RowIt row(lp); row != INVALID; ++row) {
146    dual_sum += row;
147  }
148\endcode
149
150The LP solver interface provides several other features, which are
151documented in the classes \ref LpBase and \ref LpSolver.
152For detailed documentation, see these classes in the reference manual.
153
154If you would like to use a specific solver instead of the default one,
155you can use \ref GlpkLp, \ref ClpLp, \ref CplexLp etc. instead of
156the class \ref Lp.
157
158
159[SEC]sec_lp_mip[SEC] Mixed Integer Programming
160
161LEMON also provides a similar high-level interface for mixed integer
162programming (MIP) solvers. The default MIP solver can be used through
163the class \ref Mip, while the concrete solvers are implemented in the
164classes \ref GlpkMip, \ref CbcMip, \ref CplexMip etc.
165
166The following example demonstrates the usage of the MIP solver interface.
167The whole program can be found in \ref mip_demo.cc.
168
169\dontinclude mip_demo.cc
170\skip Create
171\until }
172\until }
173
174\todo Check this demo file after closing ticket #326.
175E.g. could we write <tt>mip.sol()</tt> instead of <tt>mip.solValue()</tt>?
176Or could we write <tt>primalValue()</tt> for \c Lp in \c lp_demo.cc?
177
178In this program, the same problem is built as in the above example,
179with 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.
181
182\code
183  // Set the type of the columns
184  mip.colType(x1, Mip::INTEGER);
185  mip.colType(x2, Mip::REAL);
186\endcode
187
188Because of this integrality requirement, the results will be different
189from the LP solution.
190
191\code
192  Objective function value: 67
193  x1 = 8
194  x2 = 9
195\endcode
196
197The documnetation of the MIP solver interface can be found in the
198reference manual at the class \ref MipSolver. The common parts of the
199LP and MIP interfaces are docmented in their common ancestor class
200\ref LpBase.
201
202
203[SEC]sec_lp_optimization[SEC] Solving Complex Optimization Problems
204
205The LP and MIP solvers are powerful tools for solving various complex
206optimization problems, as well.
207The following example solves a maximum flow problem with linear
208programming, see the whole program in \re lp_maxflow_demo.cc.
209Several other graph optimization problems can also be expressed as
210linear programs and the interface provided in LEMON facilitates solving
211them easily (though usually not so efficiently as by a direct
212combinatorial method, if one exists).
213
214\dontinclude lp_maxflow_demo.cc
215\skip DIGRAPH_TYPEDEFS
216\until solve()
217
218\note This problem can be solved much more efficiently using common
219combinatorial optimization methods, such as the \ref Preflow
220"preflow push-relabel algorithm".
221
222[TRAILER]
223*/
224}
Note: See TracBrowser for help on using the repository browser.