kpeter@710
|
1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*-
|
kpeter@710
|
2 |
*
|
kpeter@710
|
3 |
* This file is a part of LEMON, a generic C++ optimization library.
|
kpeter@710
|
4 |
*
|
kpeter@710
|
5 |
* Copyright (C) 2003-2009
|
kpeter@710
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
kpeter@710
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
kpeter@710
|
8 |
*
|
kpeter@710
|
9 |
* Permission to use, modify and distribute this software is granted
|
kpeter@710
|
10 |
* provided that this copyright notice appears in all copies. For
|
kpeter@710
|
11 |
* precise terms see the accompanying LICENSE file.
|
kpeter@710
|
12 |
*
|
kpeter@710
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
kpeter@710
|
14 |
* express or implied, and with no claim as to its suitability for any
|
kpeter@710
|
15 |
* purpose.
|
kpeter@710
|
16 |
*
|
kpeter@710
|
17 |
*/
|
kpeter@710
|
18 |
|
kpeter@710
|
19 |
namespace lemon {
|
kpeter@710
|
20 |
|
kpeter@710
|
21 |
/**
|
kpeter@710
|
22 |
\page min_cost_flow Minimum Cost Flow Problem
|
kpeter@710
|
23 |
|
kpeter@710
|
24 |
\section mcf_def Definition (GEQ form)
|
kpeter@710
|
25 |
|
kpeter@710
|
26 |
The \e minimum \e cost \e flow \e problem is to find a feasible flow of
|
kpeter@710
|
27 |
minimum total cost from a set of supply nodes to a set of demand nodes
|
kpeter@710
|
28 |
in a network with capacity constraints (lower and upper bounds)
|
kpeter@710
|
29 |
and arc costs.
|
kpeter@710
|
30 |
|
kpeter@710
|
31 |
Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
|
kpeter@710
|
32 |
\f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and
|
kpeter@710
|
33 |
upper bounds for the flow values on the arcs, for which
|
kpeter@710
|
34 |
\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
|
kpeter@710
|
35 |
\f$cost: A\rightarrow\mathbf{R}\f$ denotes the cost per unit flow
|
kpeter@710
|
36 |
on the arcs and \f$sup: V\rightarrow\mathbf{R}\f$ denotes the
|
kpeter@710
|
37 |
signed supply values of the nodes.
|
kpeter@710
|
38 |
If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
|
kpeter@710
|
39 |
supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
|
kpeter@710
|
40 |
\f$-sup(u)\f$ demand.
|
kpeter@710
|
41 |
A minimum cost flow is an \f$f: A\rightarrow\mathbf{R}\f$ solution
|
kpeter@710
|
42 |
of the following optimization problem.
|
kpeter@710
|
43 |
|
kpeter@710
|
44 |
\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
|
kpeter@710
|
45 |
\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
|
kpeter@710
|
46 |
sup(u) \quad \forall u\in V \f]
|
kpeter@710
|
47 |
\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
|
kpeter@710
|
48 |
|
kpeter@710
|
49 |
The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
|
kpeter@710
|
50 |
zero or negative in order to have a feasible solution (since the sum
|
kpeter@710
|
51 |
of the expressions on the left-hand side of the inequalities is zero).
|
kpeter@710
|
52 |
It means that the total demand must be greater or equal to the total
|
kpeter@710
|
53 |
supply and all the supplies have to be carried out from the supply nodes,
|
kpeter@710
|
54 |
but there could be demands that are not satisfied.
|
kpeter@710
|
55 |
If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
|
kpeter@710
|
56 |
constraints have to be satisfied with equality, i.e. all demands
|
kpeter@710
|
57 |
have to be satisfied and all supplies have to be used.
|
kpeter@710
|
58 |
|
kpeter@710
|
59 |
|
kpeter@710
|
60 |
\section mcf_algs Algorithms
|
kpeter@710
|
61 |
|
kpeter@710
|
62 |
LEMON contains several algorithms for solving this problem, for more
|
kpeter@710
|
63 |
information see \ref min_cost_flow_algs "Minimum Cost Flow Algorithms".
|
kpeter@710
|
64 |
|
kpeter@710
|
65 |
A feasible solution for this problem can be found using \ref Circulation.
|
kpeter@710
|
66 |
|
kpeter@710
|
67 |
|
kpeter@710
|
68 |
\section mcf_dual Dual Solution
|
kpeter@710
|
69 |
|
kpeter@710
|
70 |
The dual solution of the minimum cost flow problem is represented by
|
kpeter@710
|
71 |
node potentials \f$\pi: V\rightarrow\mathbf{R}\f$.
|
kpeter@710
|
72 |
An \f$f: A\rightarrow\mathbf{R}\f$ primal feasible solution is optimal
|
kpeter@710
|
73 |
if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$ node potentials
|
kpeter@710
|
74 |
the following \e complementary \e slackness optimality conditions hold.
|
kpeter@710
|
75 |
|
kpeter@710
|
76 |
- For all \f$uv\in A\f$ arcs:
|
kpeter@710
|
77 |
- if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
|
kpeter@710
|
78 |
- if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
|
kpeter@710
|
79 |
- if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
|
kpeter@710
|
80 |
- For all \f$u\in V\f$ nodes:
|
kpeter@833
|
81 |
- \f$\pi(u)\leq 0\f$;
|
kpeter@710
|
82 |
- if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
|
kpeter@710
|
83 |
then \f$\pi(u)=0\f$.
|
kpeter@710
|
84 |
|
kpeter@710
|
85 |
Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
|
kpeter@710
|
86 |
\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
|
kpeter@710
|
87 |
\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
|
kpeter@710
|
88 |
|
kpeter@710
|
89 |
All algorithms provide dual solution (node potentials), as well,
|
kpeter@710
|
90 |
if an optimal flow is found.
|
kpeter@710
|
91 |
|
kpeter@710
|
92 |
|
kpeter@710
|
93 |
\section mcf_eq Equality Form
|
kpeter@710
|
94 |
|
kpeter@710
|
95 |
The above \ref mcf_def "definition" is actually more general than the
|
kpeter@710
|
96 |
usual formulation of the minimum cost flow problem, in which strict
|
kpeter@710
|
97 |
equalities are required in the supply/demand contraints.
|
kpeter@710
|
98 |
|
kpeter@710
|
99 |
\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
|
kpeter@710
|
100 |
\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
|
kpeter@710
|
101 |
sup(u) \quad \forall u\in V \f]
|
kpeter@710
|
102 |
\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
|
kpeter@710
|
103 |
|
kpeter@710
|
104 |
However if the sum of the supply values is zero, then these two problems
|
kpeter@710
|
105 |
are equivalent.
|
kpeter@710
|
106 |
The \ref min_cost_flow_algs "algorithms" in LEMON support the general
|
kpeter@710
|
107 |
form, so if you need the equality form, you have to ensure this additional
|
kpeter@710
|
108 |
contraint manually.
|
kpeter@710
|
109 |
|
kpeter@710
|
110 |
|
kpeter@710
|
111 |
\section mcf_leq Opposite Inequalites (LEQ Form)
|
kpeter@710
|
112 |
|
kpeter@710
|
113 |
Another possible definition of the minimum cost flow problem is
|
kpeter@710
|
114 |
when there are <em>"less or equal"</em> (LEQ) supply/demand constraints,
|
kpeter@710
|
115 |
instead of the <em>"greater or equal"</em> (GEQ) constraints.
|
kpeter@710
|
116 |
|
kpeter@710
|
117 |
\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
|
kpeter@710
|
118 |
\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq
|
kpeter@710
|
119 |
sup(u) \quad \forall u\in V \f]
|
kpeter@710
|
120 |
\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
|
kpeter@710
|
121 |
|
kpeter@710
|
122 |
It means that the total demand must be less or equal to the
|
kpeter@710
|
123 |
total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
|
kpeter@710
|
124 |
positive) and all the demands have to be satisfied, but there
|
kpeter@710
|
125 |
could be supplies that are not carried out from the supply
|
kpeter@710
|
126 |
nodes.
|
kpeter@710
|
127 |
The equality form is also a special case of this form, of course.
|
kpeter@710
|
128 |
|
kpeter@710
|
129 |
You could easily transform this case to the \ref mcf_def "GEQ form"
|
kpeter@710
|
130 |
of the problem by reversing the direction of the arcs and taking the
|
kpeter@710
|
131 |
negative of the supply values (e.g. using \ref ReverseDigraph and
|
kpeter@710
|
132 |
\ref NegMap adaptors).
|
kpeter@710
|
133 |
However \ref NetworkSimplex algorithm also supports this form directly
|
kpeter@710
|
134 |
for the sake of convenience.
|
kpeter@710
|
135 |
|
kpeter@710
|
136 |
Note that the optimality conditions for this supply constraint type are
|
kpeter@710
|
137 |
slightly differ from the conditions that are discussed for the GEQ form,
|
kpeter@710
|
138 |
namely the potentials have to be non-negative instead of non-positive.
|
kpeter@710
|
139 |
An \f$f: A\rightarrow\mathbf{R}\f$ feasible solution of this problem
|
kpeter@710
|
140 |
is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$
|
kpeter@710
|
141 |
node potentials the following conditions hold.
|
kpeter@710
|
142 |
|
kpeter@710
|
143 |
- For all \f$uv\in A\f$ arcs:
|
kpeter@710
|
144 |
- if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
|
kpeter@710
|
145 |
- if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
|
kpeter@710
|
146 |
- if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
|
kpeter@710
|
147 |
- For all \f$u\in V\f$ nodes:
|
kpeter@833
|
148 |
- \f$\pi(u)\geq 0\f$;
|
kpeter@710
|
149 |
- if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
|
kpeter@710
|
150 |
then \f$\pi(u)=0\f$.
|
kpeter@710
|
151 |
|
kpeter@710
|
152 |
*/
|
kpeter@710
|
153 |
}
|