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 \todo This page is under construction.
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.
33 Lp::Col x1 = lp.addCol();
34 Lp::Col x2 = lp.addCol();
36 lp.addRow(0 <= x1 + x2 <= 100);
37 lp.addRow(2 * x1 <= x2 + 32);
39 lp.colLowerBound(x1, 0);
40 lp.colUpperBound(x2, 100);
43 lp.obj(10 * x1 + 6 * x2);
46 cout << "Objective function value: " << lp.primal() << endl;
47 cout << "x1 = " << lp.primal(x1) << endl;
48 cout << "x2 = " << lp.primal(x2) << endl;
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.
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).
66 Digraph::ArcMap<Lp::Col> f(g);
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]);
75 // Flow conservation constraints
76 for (Digraph::NodeIt n(g); n != INVALID; ++n) {
77 if (n == src || n == trg) continue;
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];
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];
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