doc/groups.dox
 changeset 687 6c408d864fa1 parent 658 85cb3aa71cce child 698 3adf5e2d1e62 child 843 189760a7cdd0
     1.1 --- a/doc/groups.dox	Sun Apr 26 16:36:23 2009 +0100
1.2 +++ b/doc/groups.dox	Wed Apr 29 03:15:24 2009 +0200
1.3 @@ -352,17 +352,17 @@
1.4  minimum total cost from a set of supply nodes to a set of demand nodes
1.5  in a network with capacity constraints (lower and upper bounds)
1.6  and arc costs.
1.7 -Formally, let \f$G=(V,A)\f$ be a digraph,
1.8 -\f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
1.9 +Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{Z}\f$,
1.10 +\f$upper: A\rightarrow\mathbf{Z}\cup\{+\infty\}\f$ denote the lower and
1.11  upper bounds for the flow values on the arcs, for which
1.12 -\f$0 \leq lower(uv) \leq upper(uv)\f$ holds for all \f$uv\in A\f$.
1.13 -\f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
1.14 -on the arcs, and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
1.15 +\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
1.16 +\f$cost: A\rightarrow\mathbf{Z}\f$ denotes the cost per unit flow
1.17 +on the arcs and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
1.18  signed supply values of the nodes.
1.19  If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
1.20  supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
1.21  \f$-sup(u)\f$ demand.
1.22 -A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}^+_0\f$ solution
1.23 +A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution
1.24  of the following optimization problem.
1.25
1.26  \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
1.27 @@ -404,7 +404,7 @@
1.28
1.29  The dual solution of the minimum cost flow problem is represented by node
1.30  potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
1.31 -An \f$f: A\rightarrow\mathbf{Z}^+_0\f$ feasible solution of the problem
1.32 +An \f$f: A\rightarrow\mathbf{Z}\f$ feasible solution of the problem
1.33  is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
1.34  node potentials the following \e complementary \e slackness optimality
1.35  conditions hold.
1.36 @@ -413,15 +413,15 @@
1.37     - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
1.38     - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
1.39     - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
1.40 - - For all \f$u\in V\f$:
1.41 + - For all \f$u\in V\f$ nodes:
1.42     - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
1.43       then \f$\pi(u)=0\f$.
1.44
1.45  Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
1.46 -\f$uv\in A\f$ with respect to the node potentials \f$\pi\f$, i.e.
1.47 +\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
1.48  \f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
1.49
1.50 -All algorithms provide dual solution (node potentials) as well
1.51 +All algorithms provide dual solution (node potentials) as well,
1.52  if an optimal flow is found.
1.53
1.54  LEMON contains several algorithms for solving minimum cost flow problems.