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.
Contents |
Definition
Given a flow network <math>\,G(V,E)</math> with:
-
<math>\,l(u,v)</math> Lower bound on flow from node <math>u</math> to node <math>v</math>. <math>\,c(u,v)</math> Upper bound (often denoted <math>u</math> instead of <math>c</math>). <math>\,a(u,v)</math> Cost of a unit of flow on <math>(u,v)</math>.
You have the constraints
-
<math>\quad l(u,v) \leq f(u,v) \leq c(u,v)</math> <math>\ \sum_{w \in V} f(u,w) = 0</math> Flow cannot appear or disappear in nodes.
Finding a flow assignment satisfying the constraints gives a solution to the given circulation problem. In the minimum cost variant of the problem, minimise
- <math>\sum_{(u,v) \in E} a(u,v) \cdot f(u,v)</math>
Multi-commodity circulation
In a multi-commodity circulation problem, you also need to keep track of the flow of the individual commodities:
-
<math>\,f_i(u,v)</math> The flow of commodity <math>\,i</math> from <math>\,u</math> to <math>\,v</math>. <math>\,f(u,v) = \sum_i f_i(u,v)</math> The total flow.
The conservation constraint must be upheld for individually for the commodities:
-
<math>\ \sum_{w \in V} f_i(u,w) = 0</math>
Solution
For the circulation problem, many polynomial algorithms have been developed (eg, Edmonds and Karp, 1972; Tarjan 1987-1988). For the case of multiple commodities, the problem is NP-complete for integer flows[1]. For fractional flows, it is solvable in polynomial time, as you can formulate the problem as a linear program.
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.
- Multi-commodity flow - If <math>K_i(s_i,t_i,d_i)</math> denotes a demand of <math>d_i</math> for commodity <math>i</math> from <math>s_i</math> to <math>t_i</math>, create an edge <math>(t_i,s_i)</math> with <math>l(t_i,s_i) = c(t_i,s_i) = d_i</math> for all commodities <math>i</math>. Let <math>l(u,v)=0</math> for all other edges.
- Minimum cost multi-commodity flow problem - As above, but minimise the cost.
- Minimum cost flow problem - As above, with 1 commodity.
- Maximum flow problem - Set all costs to 0, and add an edge from the sink <math>t</math> to the source <math>s</math> with <math>l(t,s)=0</math>, <math>c(t,s)=</math>∞ and <math>a(t,s)=-1</math>.
- Minimum cost maximum flow problem - First find the maximum flow amount <math>m</math>. Then solve with <math>l(t,s)=c(t,s)=m</math> and <math>a(t,s)=0</math>.
- Single-source shortest path - Let <math>l(u,v)=0</math> and <math>c(u,v)=1</math> for all edges in the graph, and add an edge <math>(t,s)</math> with <math>l(t,s)=c(t,s)=1</math> and <math>a(t,s)=0</math>.
- All-pairs shortest path - Let all capacities be unlimited, and find a flow of 1 for <math>v(v-1)/2</math> commodities, one for each pair of nodes.
References
- ^ S. Even and A. Itai and A. Shamir (1976). "On the Complexity of Timetable and Multicommodity Flow Problems". SIAM Journal on Computing 5: 691-703. SIAM. doi:10.1137/0205048.
