changeset 710 8b0df68370a4
parent 707 d9cf3b5858ae
child 757 f1fe0ddad6f7
child 760 4ac30454f1c1
child 782 853fcddcf282
child 815 0a42883c8221
child 844 c01a98ce01fd
     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.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.11  \brief Algorithms for finding minimum cost flows and circulations.
    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.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.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,