COIN-OR::LEMON - Graph Library

source: lemon-tutorial/lp.dox @ 30:7d70e9735686

Last change on this file since 30:7d70e9735686 was 30:7d70e9735686, checked in by Peter Kovacs <kpeter@…>, 9 years ago

Add a preliminary page about the LP interface

File size: 3.1 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-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
19namespace lemon {
20/**
21[PAGE]sec_lp[PAGE] Linear Programming Interface
22
23\todo Clarify this section.
24
25Linear programming (LP) is one of the most important
26general methods of operations research and LP solvers are widely used in
27optimization software. The interface provided in LEMON makes it possible to
28specify 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,
52while \ref LpBase::Row "Lp::Row" represents the constraints. The numerical
53operators can be used to form expressions from columns and dual
54expressions from rows. Due to the suitable operator overloads,
55a problem can be described in C++ conveniently, directly as it is
56expressed in mathematics.
57
58
59The following example solves a maximum flow problem with linear
60programming. Several other graph optimization problems can also be
61expressed 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
94Note that LEMON does not implement an LP solver, it just wraps various
95libraries with a uniform high-level interface.
96Currently, the following linear and mixed integer programming packages are
97supported: GLPK, Clp, Cbc, ILOG CPLEX and SoPlex.
98However, additional wrapper classes for new solvers can also be implemented
99quite easily.
100
101[TRAILER]
102*/
103}
Note: See TracBrowser for help on using the repository browser.