Circulation problem

From Wikipedia, the free encyclopedia

The circulation problem and its variants is a generalisation of network flow problems, with the added constraint of a lower bound on edge flows, and with flow conservation also being required for the source and sink (i.e. there are no special nodes). In variants of the problem, you have multiple commodities flowing through the network, and a cost on the flow.

1 Definition
2 Solution
3 Related problems
4 References

[edit] Definition

Given a flow network $\,G(V,E)$ with

$\,l(u,v)$	Lower bound on flow from $u$ to $v$ .
$\,c(u,v)$	Upper bound (often denoted $u$ instead of $c$ )
$\,a(u,v)$	Cost of a unit of flow on $(u, v)$
$\,K_i = (s_i,t_i,d_i)$	The source, sink, and demand of commodity $i$
$\,f_i(u,v)$	The flow of commodity $i$ from $u$ to $v$
$\,f(u,v) = \sum_i f_i(u,v)$

You have the constraints

Capacity constraints:	$\quad l(u,v) \leq f(u,v) \leq c(u,v)$
Skew symmetry:	$\;f_i(u,v) = - f_i(v,u)$
Flow conservation:	$\ \sum_{w \in V} f_i(u,w) = 0$

In the minimum cost variant of the problem, minimise

$\sum_{(u,v) \in E} a(u,v) \cdot f(u,v)$

Note that the parameters for commodity $\,s_i,t_i,d_i$ are not used directly in the optimisation problem. To get a flow of $\,d_i$ from $\,s_i$ to $\,t_i$ , set $\,l(t_i,s_i) = c(t_i,s_i) = d_i$ .

[edit] Solution

The only known polynomial solution to any multi-commodity flow problem is linear programming^[1].

[edit] Related problems

Below are given some problems, and how to solve them with the general circulation setup given above.

Minimum cost multi-commodity circulation problem - Using all constraints given above.
Minimum cost circulation problem - Use a single commodity
Multi-commodity circulation - Solve without optimising cost.
Simple circulation - Just use one commodity, and no cost.
Minimum cost multi-commodity flow problem - Set all lower bounds to 0. Add an edge from the sink to the source with cost less that the negative sum of all other edges. Control the amount of flow by adjusting $l (t i, s i) = u (t i, s i) = d i$ .
Minimum cost flow problem - As above, with 1 commodity.
Minimum cost maximum flow problem - Let the back edge have unlimited capacity.
Maximum flow problem - Set all costs to 0, and add an edge from the sink to the source with negative cost.
Single-source shortest path - Find the cheapest flow of 1.
Multi-commodity flow - Set all costs to 0. Back-edges with $l (t i, s i) = u (t i, s i) = d i$ .
Maximum flow - Solve with 1 commodity, and maximize the flow by adding an edge $(t, s)$ with negative cost.
All-pairs shortest path - Let all capacities be unlimited, and find a flow of 1 for $v (v - 1) / 2$ commodities, one for each pair of nodes.