doc/groups.dox
changeset 642 111698359429
parent 611 85cb3aa71cce
child 651 3adf5e2d1e62
equal deleted inserted replaced
25:6449316627fe 26:18297b9fca6a
   350 
   350 
   351 The \e minimum \e cost \e flow \e problem is to find a feasible flow of
   351 The \e minimum \e cost \e flow \e problem is to find a feasible flow of
   352 minimum total cost from a set of supply nodes to a set of demand nodes
   352 minimum total cost from a set of supply nodes to a set of demand nodes
   353 in a network with capacity constraints (lower and upper bounds)
   353 in a network with capacity constraints (lower and upper bounds)
   354 and arc costs.
   354 and arc costs.
   355 Formally, let \f$G=(V,A)\f$ be a digraph,
   355 Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{Z}\f$,
   356 \f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
   356 \f$upper: A\rightarrow\mathbf{Z}\cup\{+\infty\}\f$ denote the lower and
   357 upper bounds for the flow values on the arcs, for which
   357 upper bounds for the flow values on the arcs, for which
   358 \f$0 \leq lower(uv) \leq upper(uv)\f$ holds for all \f$uv\in A\f$.
   358 \f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
   359 \f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
   359 \f$cost: A\rightarrow\mathbf{Z}\f$ denotes the cost per unit flow
   360 on the arcs, and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
   360 on the arcs and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
   361 signed supply values of the nodes.
   361 signed supply values of the nodes.
   362 If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
   362 If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
   363 supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
   363 supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
   364 \f$-sup(u)\f$ demand.
   364 \f$-sup(u)\f$ demand.
   365 A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}^+_0\f$ solution
   365 A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution
   366 of the following optimization problem.
   366 of the following optimization problem.
   367 
   367 
   368 \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
   368 \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
   369 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
   369 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
   370     sup(u) \quad \forall u\in V \f]
   370     sup(u) \quad \forall u\in V \f]
   402 are equivalent. So if you need the equality form, you have to ensure this
   402 are equivalent. So if you need the equality form, you have to ensure this
   403 additional contraint for the algorithms.
   403 additional contraint for the algorithms.
   404 
   404 
   405 The dual solution of the minimum cost flow problem is represented by node 
   405 The dual solution of the minimum cost flow problem is represented by node 
   406 potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
   406 potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
   407 An \f$f: A\rightarrow\mathbf{Z}^+_0\f$ feasible solution of the problem
   407 An \f$f: A\rightarrow\mathbf{Z}\f$ feasible solution of the problem
   408 is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
   408 is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
   409 node potentials the following \e complementary \e slackness optimality
   409 node potentials the following \e complementary \e slackness optimality
   410 conditions hold.
   410 conditions hold.
   411 
   411 
   412  - For all \f$uv\in A\f$ arcs:
   412  - For all \f$uv\in A\f$ arcs:
   413    - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
   413    - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
   414    - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
   414    - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
   415    - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
   415    - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
   416  - For all \f$u\in V\f$:
   416  - For all \f$u\in V\f$ nodes:
   417    - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
   417    - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
   418      then \f$\pi(u)=0\f$.
   418      then \f$\pi(u)=0\f$.
   419  
   419  
   420 Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
   420 Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
   421 \f$uv\in A\f$ with respect to the node potentials \f$\pi\f$, i.e.
   421 \f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
   422 \f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
   422 \f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
   423 
   423 
   424 All algorithms provide dual solution (node potentials) as well
   424 All algorithms provide dual solution (node potentials) as well,
   425 if an optimal flow is found.
   425 if an optimal flow is found.
   426 
   426 
   427 LEMON contains several algorithms for solving minimum cost flow problems.
   427 LEMON contains several algorithms for solving minimum cost flow problems.
   428  - \ref NetworkSimplex Primal Network Simplex algorithm with various
   428  - \ref NetworkSimplex Primal Network Simplex algorithm with various
   429    pivot strategies.
   429    pivot strategies.