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). A more common generalisation of this problem is the minimum cost circulation problem.

Definition

Given a flow network ${\displaystyle \,G(V,E)}$ , where edge ${\displaystyle (u,v)\in E}$  has lower and upper bounds on flow ${\displaystyle \,l(u,v)}$  and ${\displaystyle \,c(u,v)}$ . Find an assignment of flow which satisfies the constraints:

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

Relation to other problems

Generalisations are the minimum cost circulation problem and the multi-commodity circulation problem.

Solutions

Circulation problems are solved with linear programming