1.1 --- a/doc/groups.dox Fri Apr 03 18:59:15 2009 +0200
1.2 +++ b/doc/groups.dox Fri Apr 17 18:04:36 2009 +0200
1.3 @@ -317,15 +317,15 @@
1.4
1.5 The \e maximum \e flow \e problem is to find a flow of maximum value between
1.6 a single source and a single target. Formally, there is a \f$G=(V,A)\f$
1.7 -digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and
1.8 +digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
1.9 \f$s, t \in V\f$ source and target nodes.
1.10 -A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the
1.11 +A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
1.12 following optimization problem.
1.13
1.14 -\f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f]
1.15 -\f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)
1.16 - \qquad \forall v\in V\setminus\{s,t\} \f]
1.17 -\f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f]
1.18 +\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
1.19 +\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
1.20 + \quad \forall u\in V\setminus\{s,t\} \f]
1.21 +\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
1.22
1.23 LEMON contains several algorithms for solving maximum flow problems:
1.24 - \ref EdmondsKarp Edmonds-Karp algorithm.
1.25 @@ -345,35 +345,103 @@
1.26
1.27 \brief Algorithms for finding minimum cost flows and circulations.
1.28
1.29 -This group describes the algorithms for finding minimum cost flows and
1.30 +This group contains the algorithms for finding minimum cost flows and
1.31 circulations.
1.32
1.33 The \e minimum \e cost \e flow \e problem is to find a feasible flow of
1.34 minimum total cost from a set of supply nodes to a set of demand nodes
1.35 -in a network with capacity constraints and arc costs.
1.36 +in a network with capacity constraints (lower and upper bounds)
1.37 +and arc costs.
1.38 Formally, let \f$G=(V,A)\f$ be a digraph,
1.39 \f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
1.40 -upper bounds for the flow values on the arcs,
1.41 +upper bounds for the flow values on the arcs, for which
1.42 +\f$0 \leq lower(uv) \leq upper(uv)\f$ holds for all \f$uv\in A\f$.
1.43 \f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
1.44 -on the arcs, and
1.45 -\f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values
1.46 -of the nodes.
1.47 -A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of
1.48 -the following optimization problem.
1.49 +on the arcs, and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
1.50 +signed supply values of the nodes.
1.51 +If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
1.52 +supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
1.53 +\f$-sup(u)\f$ demand.
1.54 +A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}^+_0\f$ solution
1.55 +of the following optimization problem.
1.56
1.57 -\f[ \min\sum_{a\in A} f(a) cost(a) \f]
1.58 -\f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) =
1.59 - supply(v) \qquad \forall v\in V \f]
1.60 -\f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]
1.61 +\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
1.62 +\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
1.63 + sup(u) \quad \forall u\in V \f]
1.64 +\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
1.65
1.66 -LEMON contains several algorithms for solving minimum cost flow problems:
1.67 - - \ref CycleCanceling Cycle-canceling algorithms.
1.68 - - \ref CapacityScaling Successive shortest path algorithm with optional
1.69 +The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
1.70 +zero or negative in order to have a feasible solution (since the sum
1.71 +of the expressions on the left-hand side of the inequalities is zero).
1.72 +It means that the total demand must be greater or equal to the total
1.73 +supply and all the supplies have to be carried out from the supply nodes,
1.74 +but there could be demands that are not satisfied.
1.75 +If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
1.76 +constraints have to be satisfied with equality, i.e. all demands
1.77 +have to be satisfied and all supplies have to be used.
1.78 +
1.79 +If you need the opposite inequalities in the supply/demand constraints
1.80 +(i.e. the total demand is less than the total supply and all the demands
1.81 +have to be satisfied while there could be supplies that are not used),
1.82 +then you could easily transform the problem to the above form by reversing
1.83 +the direction of the arcs and taking the negative of the supply values
1.84 +(e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
1.85 +However \ref NetworkSimplex algorithm also supports this form directly
1.86 +for the sake of convenience.
1.87 +
1.88 +A feasible solution for this problem can be found using \ref Circulation.
1.89 +
1.90 +Note that the above formulation is actually more general than the usual
1.91 +definition of the minimum cost flow problem, in which strict equalities
1.92 +are required in the supply/demand contraints, i.e.
1.93 +
1.94 +\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
1.95 + sup(u) \quad \forall u\in V. \f]
1.96 +
1.97 +However if the sum of the supply values is zero, then these two problems
1.98 +are equivalent. So if you need the equality form, you have to ensure this
1.99 +additional contraint for the algorithms.
1.100 +
1.101 +The dual solution of the minimum cost flow problem is represented by node
1.102 +potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
1.103 +An \f$f: A\rightarrow\mathbf{Z}^+_0\f$ feasible solution of the problem
1.104 +is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
1.105 +node potentials the following \e complementary \e slackness optimality
1.106 +conditions hold.
1.107 +
1.108 + - For all \f$uv\in A\f$ arcs:
1.109 + - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
1.110 + - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
1.111 + - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
1.112 + - For all \f$u\in V\f$:
1.113 + - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
1.114 + then \f$\pi(u)=0\f$.
1.115 +
1.116 +Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
1.117 +\f$uv\in A\f$ with respect to the node potentials \f$\pi\f$, i.e.
1.118 +\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
1.119 +
1.120 +All algorithms provide dual solution (node potentials) as well
1.121 +if an optimal flow is found.
1.122 +
1.123 +LEMON contains several algorithms for solving minimum cost flow problems.
1.124 + - \ref NetworkSimplex Primal Network Simplex algorithm with various
1.125 + pivot strategies.
1.126 + - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
1.127 + cost scaling.
1.128 + - \ref CapacityScaling Successive Shortest %Path algorithm with optional
1.129 capacity scaling.
1.130 - - \ref CostScaling Push-relabel and augment-relabel algorithms based on
1.131 - cost scaling.
1.132 - - \ref NetworkSimplex Primal network simplex algorithm with various
1.133 - pivot strategies.
1.134 + - \ref CancelAndTighten The Cancel and Tighten algorithm.
1.135 + - \ref CycleCanceling Cycle-Canceling algorithms.
1.136 +
1.137 +Most of these implementations support the general inequality form of the
1.138 +minimum cost flow problem, but CancelAndTighten and CycleCanceling
1.139 +only support the equality form due to the primal method they use.
1.140 +
1.141 +In general NetworkSimplex is the most efficient implementation,
1.142 +but in special cases other algorithms could be faster.
1.143 +For example, if the total supply and/or capacities are rather small,
1.144 +CapacityScaling is usually the fastest algorithm (without effective scaling).
1.145 */
1.146
1.147 /**