Circulation problem
Encyclopedia
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). In variants of the problem, you have multiple commodities flowing through the network, and a cost on the flow.
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, minimise
The conservation constraint must be upheld for individually for the commodities:
, 1972; Tarjan 1987-1988).
For the case of multiple commodities, the problem is NP-complete
for integer flows. For fractional flows, it is solvable in polynomial time, as one can formulate the problem as a linear program
.
Network flow
In graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in Operations Research, a directed graph is called a network, the vertices are called nodes and the edges are...
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 is a 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, minimise
Multi-commodity circulation
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. |
The conservation constraint must be upheld for individually for the commodities:
Solution
For the circulation problem, many polynomial algorithms have been developed (e.g., Edmonds and KarpEdmonds-Karp algorithm
In computer science and graph theory, the Edmonds–Karp algorithm is an implementation of the Ford–Fulkerson method for computing the maximum flow in a flow network in O time. It is asymptotically slower than the relabel-to-front algorithm, which runs in O time, but it is often faster in...
, 1972; Tarjan 1987-1988).
For the case of multiple commodities, the problem is NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
for integer flows. For fractional flows, it is solvable in polynomial time, as one can formulate the problem as a linear program
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
.
Related problems
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 flowMulti-commodity flow problemThe multi-commodity flow problem is a network flow problem with multiple commodities flowing through the network, with different source and sink nodes.-Definition:Given a flow network \,G, where edge \in E has capacity \,c...
- 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 minimise the cost.
- Minimum cost flow problemMinimum cost flow problemThe minimum-cost flow problem is finding the cheapest possible way of sending a certain amount of flow through a flow network.- Definition :Given a flow network \,G with source s \in V and sink t \in V, where edge \in E has capacity \,c, flow \,f and cost \,a. The cost of sending this flow is f...
- As above, with 1 commodity. - Maximum flow problemMaximum flow problemIn optimization theory, the maximum flow problem is to find a feasible flow through a single-source, single-sink flow network that is maximum....
- 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 pathShortest path problemIn graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized...
- Let
and 
for all edges in the graph, and add an edge 
with 
and 
. - All-pairs shortest pathShortest path problemIn graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized...
- Let all capacities be unlimited, and find a flow of 1 for
commodities, one for each pair of nodes.