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).

Definition

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

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

Relation to other problems

Generalisations are the minimum cost circulation problem and the multicommodity circulation problem.

Solutions

Circulation problems are solved with linear programming