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

${\displaystyle l(v,w)}$ , lower bound on flow from node ${\displaystyle v}$  to node ${\displaystyle w}$ ,

${\displaystyle u(v,w)}$ , upper bound on flow from node ${\displaystyle v}$  to node ${\displaystyle w}$ ,

${\displaystyle c(v,w)}$ , cost of a unit of flow on ${\displaystyle (v,w)}$ 

and the constraints:

${\displaystyle l(v,w)\leq f(v,w)\leq u(v,w)}$ ,

${\displaystyle \sum _{w\in V}f(u,w)=0}$  (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, minimize

${\displaystyle \sum _{(v,w)\in E}c(v,w)\cdot f(v,w).}$ 

In a multi-commodity circulation problem, you also need to keep track of the flow of the individual commodities:

${\displaystyle \,f_{i}(v,w)}$	The flow of commodity ${\displaystyle i}$  from ${\displaystyle v}$  to ${\displaystyle w}$ .
${\displaystyle \,f(v,w)=\sum _{i}f_{i}(v,w)}$	The total flow.

There is also a lower bound on each flow of commodity.

${\displaystyle \,l_{i}(v,w)\leq f_{i}(v,w)}$

The conservation constraint must be upheld individually for the commodities:

${\displaystyle \ \sum _{w\in V}f_{i}(u,w)=0.}$ 

For the circulation problem, many polynomial algorithms have been developed (e.g., Edmonds–Karp algorithm, 1972; Tarjan 1987-1988). Tardos found the first strongly polynomial algorithm.^[1]

For the case of multiple commodities, the problem is NP-complete for integer flows.^[2] For fractional flows, it is solvable in polynomial time, as one can formulate the problem as a linear program.

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 ${\displaystyle K_{i}(s_{i},t_{i},d_{i})}$  denotes a demand of ${\displaystyle d_{i}}$  for commodity ${\displaystyle i}$  from ${\displaystyle s_{i}}$  to ${\displaystyle t_{i}}$ , create an edge ${\displaystyle (t_{i},s_{i})}$  with ${\displaystyle l_{i}(t_{i},s_{i})=u(t_{i},s_{i})=d_{i}}$  for all commodities ${\displaystyle i}$ . Let ${\displaystyle l_{i}(u,v)=0}$  for all other edges.
• Minimum cost multi-commodity flow problem - As above, but minimize 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 ${\displaystyle t}$  to the source ${\displaystyle s}$  with ${\displaystyle l(t,s)=0}$ , ${\displaystyle u(t,s)=}$ ∞ and ${\displaystyle c(t,s)=-1}$ .
• Minimum cost maximum flow problem - First find the maximum flow amount ${\displaystyle m}$ . Then solve with ${\displaystyle l(t,s)=u(t,s)=m}$  and ${\displaystyle c(t,s)=0}$ .
• Single-source shortest path - Let ${\displaystyle l(u,v)=0}$  and ${\displaystyle c(u,v)=1}$  for all edges in the graph, and add an edge ${\displaystyle (t,s)}$  with ${\displaystyle l(t,s)=u(t,s)=1}$  and ${\displaystyle c(t,s)=0}$ .
• 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.