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