1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2010
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
21 [PAGE]sec_lp[PAGE] Linear Programming Interface
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.
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.
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
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
55 Lp::Col x1 = lp.addCol();
56 Lp::Col x2 = lp.addCol();
58 lp.addRow(0 <= x1 + x2 <= 100);
59 lp.addRow(2 * x1 <= x2 + 32);
61 lp.colLowerBound(x1, 0);
62 lp.colUpperBound(x2, 100);
65 lp.obj(10 * x1 + 6 * x2);
68 cout << "Objective function value: " << lp.primal() << endl;
69 cout << "x1 = " << lp.primal(x1) << endl;
70 cout << "x2 = " << lp.primal(x2) << endl;
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.
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).
87 ListDigraph::ArcMap<Lp::Col> f(g);
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]);
96 // Flow conservation constraints
97 for (ListDigraph::NodeIt n(g); n != INVALID; ++n) {
98 if (n == src || n == trg) continue;
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];
105 // Objective function
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];