doc/min_cost_flow.dox
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 10 Oct 2009 08:18:46 +0200
changeset 802 134852d7fb0a
parent 710 8b0df68370a4
child 835 c92296660262
permissions -rw-r--r--
Insert citations into the doc (#184)

- Add general citations to modules.
- Add specific citations for max flow and min cost flow algorithms.
- Add citations for the supported LP and MIP solvers.
- Extend the main page.
- Replace inproceedings entries with the journal versions.
- Add a new bibtex entry about network simplex.
- Remove unwanted entries.
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@802
    29
and arc costs \ref amo93networkflows.
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@710
    81
   - \f$\pi(u)<=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@710
   148
   - \f$\pi(u)>=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
}