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 | In this section, we will show two examples. The first one shows how simple |
---|
48 | it is to formalize and solve an LP problem in LEMON, while the second one |
---|
49 | shows how LEMON facilitates solving network optimization problems using LP |
---|
50 | solvers. |
---|
51 | |
---|
52 | \code |
---|
53 | Lp lp; |
---|
54 | |
---|
55 | Lp::Col x1 = lp.addCol(); |
---|
56 | Lp::Col x2 = lp.addCol(); |
---|
57 | |
---|
58 | lp.addRow(0 <= x1 + x2 <= 100); |
---|
59 | lp.addRow(2 * x1 <= x2 + 32); |
---|
60 | |
---|
61 | lp.colLowerBound(x1, 0); |
---|
62 | lp.colUpperBound(x2, 100); |
---|
63 | |
---|
64 | lp.max(); |
---|
65 | lp.obj(10 * x1 + 6 * x2); |
---|
66 | lp.solve(); |
---|
67 | |
---|
68 | std::cout << "Objective function value: " << lp.primal() << std::endl; |
---|
69 | std::cout << "x1 = " << lp.primal(x1) << std::endl; |
---|
70 | std::cout << "x2 = " << lp.primal(x2) << std::endl; |
---|
71 | \endcode |
---|
72 | |
---|
73 | \ref LpBase::Col "Lp::Col" type represents the variables in the LP problems, |
---|
74 | while \ref LpBase::Row "Lp::Row" represents the constraints. The numerical |
---|
75 | operators can be used to form expressions from columns and dual |
---|
76 | expressions from rows. Due to the suitable operator overloads, |
---|
77 | a problem can be described in C++ conveniently, directly as it is |
---|
78 | expressed in mathematics. |
---|
79 | |
---|
80 | The following example solves a maximum flow problem with linear |
---|
81 | programming. Several other graph optimization problems can also be |
---|
82 | expressed as linear programs and this interface helps to solve them easily |
---|
83 | (though usually not so efficiently as by a direct combinatorial method). |
---|
84 | |
---|
85 | \code |
---|
86 | Lp lp; |
---|
87 | ListDigraph::ArcMap<Lp::Col> f(g); |
---|
88 | lp.addColSet(f); |
---|
89 | |
---|
90 | // Capacity constraints |
---|
91 | for (ListDigraph::ArcIt a(g); a != INVALID; ++a) { |
---|
92 | lp.colLowerBound(f[a], 0); |
---|
93 | lp.colUpperBound(f[a], capacity[a]); |
---|
94 | } |
---|
95 | |
---|
96 | // Flow conservation constraints |
---|
97 | for (ListDigraph::NodeIt n(g); n != INVALID; ++n) { |
---|
98 | if (n == src || n == trg) continue; |
---|
99 | Lp::Expr e; |
---|
100 | for (ListDigraph::OutArcIt a(g,n); a != INVALID; ++a) e += f[a]; |
---|
101 | for (ListDigraph::InArcIt a(g,n); a != INVALID; ++a) e -= f[a]; |
---|
102 | lp.addRow(e == 0); |
---|
103 | } |
---|
104 | |
---|
105 | // Objective function |
---|
106 | Lp::Expr o; |
---|
107 | for (ListDigraph::OutArcIt a(g,src); a != INVALID; ++a) o += f[a]; |
---|
108 | for (ListDigraph::InArcIt a(g,src); a != INVALID; ++a) o -= f[a]; |
---|
109 | |
---|
110 | lp.max(); |
---|
111 | lp.obj(o); |
---|
112 | lp.solve(); |
---|
113 | |
---|
114 | std::cout << "Max flow value: " << lp.primal() << std::endl; |
---|
115 | \endcode |
---|
116 | |
---|
117 | [TRAILER] |
---|
118 | */ |
---|
119 | } |
---|