COIN-OR::LEMON - Graph Library

source: lemon-tutorial/lp.dox @ 49:c8c5a2a4ec71

Last change on this file since 49:c8c5a2a4ec71 was 48:a5457a780c34, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Clarify and extend the LP section

File size: 3.9 KB
Line 
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
19namespace lemon {
20/**
21[PAGE]sec_lp[PAGE] Linear Programming Interface
22
23Linear programming (LP) is one of the most important general methods of
24operations research. Countless optimization problems can be formulated
25and solved using LP techniques.
26Therefore, developing efficient LP solvers has been of high practical
27interest for a long time.
28Nowadays various efficient LP solvers are available, including both
29open source and commercial software packages.
30Therefore, LEMON does not implement its own solver, but it features
31wrapper classes for several known LP packages providing a common
32high-level interface for all of them.
33
34The advantage of this approach is twofold. First, our C++ interface is
35more comfortable than the typical native interfaces of the solvers.
36Second, changing the underlying solver in a certain application using
37LEMON's LP interface needs no effort. So, for example, one may try her
38idea using an open source solver, demonstrate its usability for a customer
39and if it works well, but the performance should be improved, then the
40customer may decide to purchase and use a better commercial solver.
41
42Currently, the following linear and mixed integer programming packages are
43supported: GLPK, Clp, Cbc, ILOG CPLEX and SoPlex.
44However, additional wrapper classes for new solvers can also be implemented
45quite easily.
46
47In this section, we will show two examples. The first one shows how simple
48it is to formalize and solve an LP problem in LEMON, while the second one
49shows how LEMON facilitates solving network optimization problems using LP
50solvers.
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  cout << "Objective function value: " << lp.primal() << endl;
69  cout << "x1 = " << lp.primal(x1) << endl;
70  cout << "x2 = " << lp.primal(x2) << endl;
71\endcode
72
73\ref LpBase::Col "Lp::Col" type represents the variables in the LP problems,
74while \ref LpBase::Row "Lp::Row" represents the constraints. The numerical
75operators can be used to form expressions from columns and dual
76expressions from rows. Due to the suitable operator overloads,
77a problem can be described in C++ conveniently, directly as it is
78expressed in mathematics.
79
80The following example solves a maximum flow problem with linear
81programming. Several other graph optimization problems can also be
82expressed 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\endcode
114
115[TRAILER]
116*/
117}
Note: See TracBrowser for help on using the repository browser.