COIN-OR::LEMON - Graph Library

source: lemon/doc/min_cost_flow.dox @ 710:8b0df68370a4

Last change on this file since 710:8b0df68370a4 was 710:8b0df68370a4, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Fix the GEQ/LEQ handling in NetworkSimplex? + improve doc (#291)

  • Fix the optimality conditions for the GEQ/LEQ form.
  • Fix the initialization of the algortihm. It ensures correct solutions and it is much faster for the inequality forms.
  • Fix the pivot rules to search all the arcs that have to be allowed to get in the basis.
  • Better block size for the Block Search pivot rule.
  • Improve documentation of the problem and move it to a separate page.
File size: 6.1 KB
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 */
19namespace lemon {
22\page min_cost_flow Minimum Cost Flow Problem
24\section mcf_def Definition (GEQ form)
26The \e minimum \e cost \e flow \e problem is to find a feasible flow of
27minimum total cost from a set of supply nodes to a set of demand nodes
28in a network with capacity constraints (lower and upper bounds)
29and arc costs.
31Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
32\f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and
33upper bounds for the flow values on the arcs, for which
34\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
35\f$cost: A\rightarrow\mathbf{R}\f$ denotes the cost per unit flow
36on the arcs and \f$sup: V\rightarrow\mathbf{R}\f$ denotes the
37signed supply values of the nodes.
38If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
39supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
40\f$-sup(u)\f$ demand.
41A minimum cost flow is an \f$f: A\rightarrow\mathbf{R}\f$ solution
42of the following optimization problem.
44\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
45\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
46    sup(u) \quad \forall u\in V \f]
47\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
49The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
50zero or negative in order to have a feasible solution (since the sum
51of the expressions on the left-hand side of the inequalities is zero).
52It means that the total demand must be greater or equal to the total
53supply and all the supplies have to be carried out from the supply nodes,
54but there could be demands that are not satisfied.
55If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
56constraints have to be satisfied with equality, i.e. all demands
57have to be satisfied and all supplies have to be used.
60\section mcf_algs Algorithms
62LEMON contains several algorithms for solving this problem, for more
63information see \ref min_cost_flow_algs "Minimum Cost Flow Algorithms".
65A feasible solution for this problem can be found using \ref Circulation.
68\section mcf_dual Dual Solution
70The dual solution of the minimum cost flow problem is represented by
71node potentials \f$\pi: V\rightarrow\mathbf{R}\f$.
72An \f$f: A\rightarrow\mathbf{R}\f$ primal feasible solution is optimal
73if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$ node potentials
74the following \e complementary \e slackness optimality conditions hold.
76 - For all \f$uv\in A\f$ arcs:
77   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
78   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
79   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
80 - For all \f$u\in V\f$ nodes:
81   - \f$\pi(u)<=0\f$;
82   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
83     then \f$\pi(u)=0\f$.
85Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
86\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
87\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
89All algorithms provide dual solution (node potentials), as well,
90if an optimal flow is found.
93\section mcf_eq Equality Form
95The above \ref mcf_def "definition" is actually more general than the
96usual formulation of the minimum cost flow problem, in which strict
97equalities are required in the supply/demand contraints.
99\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
100\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
101    sup(u) \quad \forall u\in V \f]
102\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
104However if the sum of the supply values is zero, then these two problems
105are equivalent.
106The \ref min_cost_flow_algs "algorithms" in LEMON support the general
107form, so if you need the equality form, you have to ensure this additional
108contraint manually.
111\section mcf_leq Opposite Inequalites (LEQ Form)
113Another possible definition of the minimum cost flow problem is
114when there are <em>"less or equal"</em> (LEQ) supply/demand constraints,
115instead of the <em>"greater or equal"</em> (GEQ) constraints.
117\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
118\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq
119    sup(u) \quad \forall u\in V \f]
120\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
122It means that the total demand must be less or equal to the
123total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
124positive) and all the demands have to be satisfied, but there
125could be supplies that are not carried out from the supply
127The equality form is also a special case of this form, of course.
129You could easily transform this case to the \ref mcf_def "GEQ form"
130of the problem by reversing the direction of the arcs and taking the
131negative of the supply values (e.g. using \ref ReverseDigraph and
132\ref NegMap adaptors).
133However \ref NetworkSimplex algorithm also supports this form directly
134for the sake of convenience.
136Note that the optimality conditions for this supply constraint type are
137slightly differ from the conditions that are discussed for the GEQ form,
138namely the potentials have to be non-negative instead of non-positive.
139An \f$f: A\rightarrow\mathbf{R}\f$ feasible solution of this problem
140is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$
141node potentials the following conditions hold.
143 - For all \f$uv\in A\f$ arcs:
144   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
145   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
146   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
147 - For all \f$u\in V\f$ nodes:
148   - \f$\pi(u)>=0\f$;
149   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
150     then \f$\pi(u)=0\f$.
Note: See TracBrowser for help on using the repository browser.