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