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.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.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.23  LEMON contains several algorithms for solving maximum flow problems:
    1.24  - \ref EdmondsKarp Edmonds-Karp algorithm.
    1.25 @@ -350,30 +350,98 @@
    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.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.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.141  /**