Circulation problem

The circulation problem and its variants are 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 multiple commodities flowing through the network, and a cost on the flow.

Definition

Given flow network G(V,E) with:

l(v,w), lower bound on flow from node v to node w,
u(v,w), upper bound on flow from node v to node w,
c(v,w), cost of a unit of flow on (v,w)

and the constraints:

l(v,w) \leq f(v,w) \leq u(v,w),
\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

\sum_{(v,w) \in E} c(v,w) \cdot f(v,w).

Multi-commodity circulation

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

\,f_i(v,w) The flow of commodity i from v to w.
\,f(v,w) = \sum_i f_i(v,w) The total flow.

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

\,l_i(v,w) \leq f_i(v,w)

The conservation constraint must be upheld individually for the commodities:

\ \sum_{w \in V} f_i(u,w) = 0.

Solution

For the circulation problem, many polynomial algorithms have been developed (e.g., Edmonds and 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.

Related problems

Below are given some problems, and how to solve them with the general circulation setup given above.

References

  1. Éva Tardos. "A strongly polynomial minimum cost circulation algorithm". Combinatorica 5: 247–255. doi:10.1007/BF02579369.
  2. S. Even and A. Itai and A. Shamir (1976). "On the complexity of time table and multi-commodity flow problems". SIAM Journal on Computing (SIAM) 5 (4): 691–703. doi:10.1137/0205048.
This article is issued from Wikipedia - version of the Thursday, March 31, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.