diff --git a/doc/groups.dox b/doc/groups.dox --- a/doc/groups.dox +++ b/doc/groups.dox @@ -317,15 +317,15 @@ The \e maximum \e flow \e problem is to find a flow of maximum value between a single source and a single target. Formally, there is a \f$G=(V,A)\f$ -digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and +digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and \f$s, t \in V\f$ source and target nodes. -A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the +A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the following optimization problem. -\f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f] -\f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a) - \qquad \forall v\in V\setminus\{s,t\} \f] -\f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f] +\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f] +\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu) + \quad \forall u\in V\setminus\{s,t\} \f] +\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] LEMON contains several algorithms for solving maximum flow problems: - \ref EdmondsKarp Edmonds-Karp algorithm. @@ -345,35 +345,103 @@ \brief Algorithms for finding minimum cost flows and circulations. -This group describes the algorithms for finding minimum cost flows and +This group contains the algorithms for finding minimum cost flows and circulations. The \e minimum \e cost \e flow \e problem is to find a feasible flow of minimum total cost from a set of supply nodes to a set of demand nodes -in a network with capacity constraints and arc costs. +in a network with capacity constraints (lower and upper bounds) +and arc costs. Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and -upper bounds for the flow values on the arcs, +upper bounds for the flow values on the arcs, for which +\f$0 \leq lower(uv) \leq upper(uv)\f$ holds for all \f$uv\in A\f$. \f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow -on the arcs, and -\f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values -of the nodes. -A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of -the following optimization problem. +on the arcs, and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the +signed supply values of the nodes. +If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$ +supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with +\f$-sup(u)\f$ demand. +A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}^+_0\f$ solution +of the following optimization problem. -\f[ \min\sum_{a\in A} f(a) cost(a) \f] -\f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) = - supply(v) \qquad \forall v\in V \f] -\f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f] +\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f] +\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq + sup(u) \quad \forall u\in V \f] +\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f] -LEMON contains several algorithms for solving minimum cost flow problems: - - \ref CycleCanceling Cycle-canceling algorithms. - - \ref CapacityScaling Successive shortest path algorithm with optional +The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be +zero or negative in order to have a feasible solution (since the sum +of the expressions on the left-hand side of the inequalities is zero). +It means that the total demand must be greater or equal to the total +supply and all the supplies have to be carried out from the supply nodes, +but there could be demands that are not satisfied. +If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand +constraints have to be satisfied with equality, i.e. all demands +have to be satisfied and all supplies have to be used. + +If you need the opposite inequalities in the supply/demand constraints +(i.e. the total demand is less than the total supply and all the demands +have to be satisfied while there could be supplies that are not used), +then you could easily transform the problem to the above form by reversing +the direction of the arcs and taking the negative of the supply values +(e.g. using \ref ReverseDigraph and \ref NegMap adaptors). +However \ref NetworkSimplex algorithm also supports this form directly +for the sake of convenience. + +A feasible solution for this problem can be found using \ref Circulation. + +Note that the above formulation is actually more general than the usual +definition of the minimum cost flow problem, in which strict equalities +are required in the supply/demand contraints, i.e. + +\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) = + sup(u) \quad \forall u\in V. \f] + +However if the sum of the supply values is zero, then these two problems +are equivalent. So if you need the equality form, you have to ensure this +additional contraint for the algorithms. + +The dual solution of the minimum cost flow problem is represented by node +potentials \f$\pi: V\rightarrow\mathbf{Z}\f$. +An \f$f: A\rightarrow\mathbf{Z}^+_0\f$ feasible solution of the problem +is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$ +node potentials the following \e complementary \e slackness optimality +conditions hold. + + - For all \f$uv\in A\f$ arcs: + - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$; + - if \f$lower(uv)