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 | |
---|
19 | namespace lemon { |
---|
20 | /** |
---|
21 | [PAGE]sec_lp[PAGE] Linear Programming Interface |
---|
22 | |
---|
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. |
---|
33 | |
---|
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. |
---|
41 | |
---|
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 |
---|
45 | quite easily. |
---|
46 | |
---|
47 | [SEC]sec_lp_basics[SEC] Basic LP Features |
---|
48 | |
---|
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. |
---|
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) |
---|
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()". |
---|
68 | |
---|
69 | The above problem has an optimal solution. If you execute this example, |
---|
70 | it 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 | |
---|
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 |
---|
81 | out this line. |
---|
82 | |
---|
83 | \code |
---|
84 | Optimal solution found. |
---|
85 | \endcode |
---|
86 | |
---|
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 |
---|
90 | \code |
---|
91 | lp.addRow(x1 - 5 <= x2); |
---|
92 | \endcode |
---|
93 | can 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 | |
---|
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. |
---|
107 | |
---|
108 | \code |
---|
109 | Lp::Expr sum; |
---|
110 | for (Lp::ColIt col(lp); col != INVALID; ++col) { |
---|
111 | sum += col; |
---|
112 | } |
---|
113 | \endcode |
---|
114 | |
---|
115 | After solving the problem, you can query the value of any primal expression, |
---|
116 | not 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 | |
---|
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. |
---|
127 | |
---|
128 | \code |
---|
129 | Lp::Row r = lp.addRow(x2 >= 3); |
---|
130 | \endcode |
---|
131 | |
---|
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). |
---|
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 |
---|
141 | from 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 | |
---|
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. |
---|
153 | |
---|
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 |
---|
156 | the class \ref Lp. |
---|
157 | |
---|
158 | |
---|
159 | [SEC]sec_lp_mip[SEC] Mixed Integer Programming |
---|
160 | |
---|
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. |
---|
165 | |
---|
166 | The following example demonstrates the usage of the MIP solver interface. |
---|
167 | The 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. |
---|
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? |
---|
177 | |
---|
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. |
---|
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 | |
---|
188 | Because of this integrality requirement, the results will be different |
---|
189 | from the LP solution. |
---|
190 | |
---|
191 | \code |
---|
192 | Objective function value: 67 |
---|
193 | x1 = 8 |
---|
194 | x2 = 9 |
---|
195 | \endcode |
---|
196 | |
---|
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 |
---|
200 | \ref LpBase. |
---|
201 | |
---|
202 | |
---|
203 | [SEC]sec_lp_optimization[SEC] Solving Complex Optimization Problems |
---|
204 | |
---|
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). |
---|
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 |
---|
219 | combinatorial optimization methods, such as the \ref Preflow |
---|
220 | "preflow push-relabel algorithm". |
---|
221 | |
---|
222 | [TRAILER] |
---|
223 | */ |
---|
224 | } |
---|