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, there are multiple commodities flowing through the network, and a cost on the flow.

Definition

edit

Given flow network   with:

 , lower bound on flow from node   to node  ,
 , upper bound on flow from node   to node  ,
 , cost of a unit of flow on  

and the constraints:

 ,
  (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

 

Multi-commodity circulation

edit

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

  The flow of commodity   from   to  .
  The total flow.

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

 

The conservation constraint must be upheld individually for the commodities:

 

Solution

edit

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.

edit

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   denotes a demand of   for commodity   from   to  , create an edge   with   for all commodities  . Let   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   to the source   with  ,  ∞ and  .
  • Minimum cost maximum flow problem - First find the maximum flow amount  . Then solve with   and  .
  • Single-source shortest path - Let   and   for all edges in the graph, and add an edge   with   and  .
  • All-pairs shortest path - Let all capacities be unlimited, and find a flow of 1 for   commodities, one for each pair of nodes.

References

edit
  1. ^ Éva Tardos (1985). "A strongly polynomial minimum cost circulation algorithm". Combinatorica. 5 (3): 247–255. doi:10.1007/BF02579369.
  2. ^ S. Even and A. Itai and A. Shamir (1976). "On the complexity of timetable and multi-commodity flow problems". SIAM Journal on Computing. 5 (4). SIAM: 691–703. doi:10.1137/0205048. Archived from the original on 2013-01-12.