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 | } |
---|