1.1 --- a/doc/groups.dox Mon May 11 16:38:21 2009 +0100
1.2 +++ b/doc/groups.dox Tue May 12 12:06:40 2009 +0200
1.3 @@ -335,91 +335,16 @@
1.4 */
1.5
1.6 /**
1.7 -@defgroup min_cost_flow Minimum Cost Flow Algorithms
1.8 +@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
1.9 @ingroup algs
1.10
1.11 \brief Algorithms for finding minimum cost flows and circulations.
1.12
1.13 This group contains the algorithms for finding minimum cost flows and
1.14 -circulations.
1.15 +circulations. For more information about this problem and its dual
1.16 +solution see \ref min_cost_flow "Minimum Cost Flow Problem".
1.17
1.18 -The \e minimum \e cost \e flow \e problem is to find a feasible flow of
1.19 -minimum total cost from a set of supply nodes to a set of demand nodes
1.20 -in a network with capacity constraints (lower and upper bounds)
1.21 -and arc costs.
1.22 -Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{Z}\f$,
1.23 -\f$upper: A\rightarrow\mathbf{Z}\cup\{+\infty\}\f$ denote the lower and
1.24 -upper bounds for the flow values on the arcs, for which
1.25 -\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
1.26 -\f$cost: A\rightarrow\mathbf{Z}\f$ denotes the cost per unit flow
1.27 -on the arcs and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
1.28 -signed supply values of the nodes.
1.29 -If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
1.30 -supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
1.31 -\f$-sup(u)\f$ demand.
1.32 -A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution
1.33 -of the following optimization problem.
1.34 -
1.35 -\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
1.36 -\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
1.37 - sup(u) \quad \forall u\in V \f]
1.38 -\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
1.39 -
1.40 -The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
1.41 -zero or negative in order to have a feasible solution (since the sum
1.42 -of the expressions on the left-hand side of the inequalities is zero).
1.43 -It means that the total demand must be greater or equal to the total
1.44 -supply and all the supplies have to be carried out from the supply nodes,
1.45 -but there could be demands that are not satisfied.
1.46 -If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
1.47 -constraints have to be satisfied with equality, i.e. all demands
1.48 -have to be satisfied and all supplies have to be used.
1.49 -
1.50 -If you need the opposite inequalities in the supply/demand constraints
1.51 -(i.e. the total demand is less than the total supply and all the demands
1.52 -have to be satisfied while there could be supplies that are not used),
1.53 -then you could easily transform the problem to the above form by reversing
1.54 -the direction of the arcs and taking the negative of the supply values
1.55 -(e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
1.56 -However \ref NetworkSimplex algorithm also supports this form directly
1.57 -for the sake of convenience.
1.58 -
1.59 -A feasible solution for this problem can be found using \ref Circulation.
1.60 -
1.61 -Note that the above formulation is actually more general than the usual
1.62 -definition of the minimum cost flow problem, in which strict equalities
1.63 -are required in the supply/demand contraints, i.e.
1.64 -
1.65 -\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
1.66 - sup(u) \quad \forall u\in V. \f]
1.67 -
1.68 -However if the sum of the supply values is zero, then these two problems
1.69 -are equivalent. So if you need the equality form, you have to ensure this
1.70 -additional contraint for the algorithms.
1.71 -
1.72 -The dual solution of the minimum cost flow problem is represented by node
1.73 -potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
1.74 -An \f$f: A\rightarrow\mathbf{Z}\f$ feasible solution of the problem
1.75 -is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
1.76 -node potentials the following \e complementary \e slackness optimality
1.77 -conditions hold.
1.78 -
1.79 - - For all \f$uv\in A\f$ arcs:
1.80 - - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
1.81 - - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
1.82 - - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
1.83 - - For all \f$u\in V\f$ nodes:
1.84 - - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
1.85 - then \f$\pi(u)=0\f$.
1.86 -
1.87 -Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
1.88 -\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
1.89 -\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
1.90 -
1.91 -All algorithms provide dual solution (node potentials) as well,
1.92 -if an optimal flow is found.
1.93 -
1.94 -LEMON contains several algorithms for solving minimum cost flow problems.
1.95 +LEMON contains several algorithms for this problem.
1.96 - \ref NetworkSimplex Primal Network Simplex algorithm with various
1.97 pivot strategies.
1.98 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
1.99 @@ -429,10 +354,6 @@
1.100 - \ref CancelAndTighten The Cancel and Tighten algorithm.
1.101 - \ref CycleCanceling Cycle-Canceling algorithms.
1.102
1.103 -Most of these implementations support the general inequality form of the
1.104 -minimum cost flow problem, but CancelAndTighten and CycleCanceling
1.105 -only support the equality form due to the primal method they use.
1.106 -
1.107 In general NetworkSimplex is the most efficient implementation,
1.108 but in special cases other algorithms could be faster.
1.109 For example, if the total supply and/or capacities are rather small,