Circulation problem

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 multiplem commodities flowing through the network, and a cost on the flow.

Definition

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

${\displaystyle \,l(u,v)}$	Lower bound on flow from ${\displaystyle u}$  to ${\displaystyle v}$ .
${\displaystyle \,c(u,v)}$	Upper bound (often denoted ${\displaystyle u}$  instead of ${\displaystyle c}$ )
${\displaystyle \,a(u,v)}$	Cost of a unit of flow on ${\displaystyle (u,v)}$
${\displaystyle \,K_{i}=(s_{i},t_{i},d_{i})}$	The source, sink, and demand of commodity ${\displaystyle i}$
${\displaystyle \,f_{i}(u,v)}$	The flow of commodity ${\displaystyle i}$  from ${\displaystyle u}$  to ${\displaystyle v}$
${\displaystyle \,f(u,v)=\sum _{i}f_{i}(u,v)}$

You have the constraints

${\displaystyle \,f_{i}(u,v)=-f_{i}(v,u)}$	Skew symmetry
${\displaystyle \,l(u,v)\leq f(u,v)\leq c(u,v)}$	Capacity constraints
${\displaystyle \,\sum _{w\in V}f_{i}(u,w)=0}$	Flow conservation

Minimise

${\displaystyle \sum _{(u,v)\in E}a(u,v)\cdot f(u,v)}$ 

Solution

The only known solution to this problem is linear programming^[1].

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
• 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 ${\displaystyle l(t_{i},s_{i})=u(t_{i},s_{i})=d_{i}}$ .
• Minimum cost flow problem. As above, with 1 commodity.
• 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. Set all capacities to 1, and find the cheapest flow of 1.
• Multi-commodity flow. Set all costs to 0. Back-edges with ${\displaystyle l(t_{i},s_{i})=u(t_{i},s_{i})=d_{i}}$ .
• Maximum flow. Solve with 1 commodity, and maximize the flow by adding ${\displaystyle (t,s)}$  with negative cost.
• All-pairs shortest path. Let all capacities be unlimited, and find a flow of 1 for ${\displaystyle v(v-1)/2}$  commodities, one for each pair of nodes.

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001) [1990]. "29". Introduction to Algorithms (2nd edition ed.). MIT Press and McGraw-Hill. pp. 788–789. ISBN 0-262-03293-7. {{cite book}}: |edition= has extra text (help)