Circulation problem

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

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.