|
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-2009 |
|
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 \todo Clarify this section. |
|
24 |
|
25 Linear programming (LP) is one of the most important |
|
26 general methods of operations research and LP solvers are widely used in |
|
27 optimization software. The interface provided in LEMON makes it possible to |
|
28 specify LP problems using a high-level syntax. |
|
29 |
|
30 \code |
|
31 Lp lp; |
|
32 |
|
33 Lp::Col x1 = lp.addCol(); |
|
34 Lp::Col x2 = lp.addCol(); |
|
35 |
|
36 lp.addRow(0 <= x1 + x2 <= 100); |
|
37 lp.addRow(2 * x1 <= x2 + 32); |
|
38 |
|
39 lp.colLowerBound(x1, 0); |
|
40 lp.colUpperBound(x2, 100); |
|
41 |
|
42 lp.max(); |
|
43 lp.obj(10 * x1 + 6 * x2); |
|
44 lp.solve(); |
|
45 |
|
46 cout << "Objective function value: " << lp.primal() << endl; |
|
47 cout << "x1 = " << lp.primal(x1) << endl; |
|
48 cout << "x2 = " << lp.primal(x2) << endl; |
|
49 \endcode |
|
50 |
|
51 \ref LpBase::Col "Lp::Col" type represents the variables in the LP problems, |
|
52 while \ref LpBase::Row "Lp::Row" represents the constraints. The numerical |
|
53 operators can be used to form expressions from columns and dual |
|
54 expressions from rows. Due to the suitable operator overloads, |
|
55 a problem can be described in C++ conveniently, directly as it is |
|
56 expressed in mathematics. |
|
57 |
|
58 |
|
59 The following example solves a maximum flow problem with linear |
|
60 programming. Several other graph optimization problems can also be |
|
61 expressed as linear programs and this interface helps to solve them easily |
|
62 (though usually not so efficiently as by a direct combinatorial method). |
|
63 |
|
64 \code |
|
65 Lp lp; |
|
66 Digraph::ArcMap<Lp::Col> f(g); |
|
67 lp.addColSet(f); |
|
68 |
|
69 // Capacity constraints |
|
70 for (Digraph::ArcIt a(g); a != INVALID; ++a) { |
|
71 lp.colLowerBound(f[a], 0); |
|
72 lp.colUpperBound(f[a], capacity[a]); |
|
73 } |
|
74 |
|
75 // Flow conservation constraints |
|
76 for (Digraph::NodeIt n(g); n != INVALID; ++n) { |
|
77 if (n == src || n == trg) continue; |
|
78 Lp::Expr e; |
|
79 for (Digraph::OutArcIt a(g,n); a != INVALID; ++a) e += f[a]; |
|
80 for (Digraph::InArcIt a(g,n); a != INVALID; ++a) e -= f[a]; |
|
81 lp.addRow(e == 0); |
|
82 } |
|
83 |
|
84 // Objective function |
|
85 Lp::Expr o; |
|
86 for (Digraph::OutArcIt a(g,src); a != INVALID; ++a) o += f[a]; |
|
87 for (Digraph::InArcIt a(g,src); a != INVALID; ++a) o -= f[a]; |
|
88 |
|
89 lp.max(); |
|
90 lp.obj(o); |
|
91 lp.solve(); |
|
92 \endcode |
|
93 |
|
94 Note that LEMON does not implement an LP solver, it just wraps various |
|
95 libraries with a uniform high-level interface. |
|
96 Currently, the following linear and mixed integer programming packages are |
|
97 supported: GLPK, Clp, Cbc, ILOG CPLEX and SoPlex. |
|
98 However, additional wrapper classes for new solvers can also be implemented |
|
99 quite easily. |
|
100 |
|
101 [TRAILER] |
|
102 */ |
|
103 } |