summary |
shortlog |
changelog |
graph |
tags |
bookmarks |
branches |
files |
changeset |
file |
latest |
revisions |
annotate |
diff |
comparison |
raw |
help

doc/groups.dox

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.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,