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
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
In a multi-commodity circulation problem, you also need to keep track of the flow of the individual commodities:
:
There is also a lower bound on each flow of commodity.
:
The conservation constraint must be upheld individually for the commodities:
:
Solution
For the circulation problem, many polynomial algorithms have been developed (e.g.,
Edmonds–Karp algorithm
In computer science, the Edmonds–Karp algorithm is an implementation of the Ford–Fulkerson method for computing the maximum flow in a flow network in O(, V, , E, ^2) time. The algorithm was first published by Yefim Dinitz (whose name is also ...
, 1972; Tarjan 1987-1988). Tardos found the first strongly polynomial algorithm.
For the case of multiple commodities, the problem is
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
for integer flows.
[{{cite journal , author = S. Even and A. Itai and A. Shamir , title = On the complexity of time table and multi-commodity flow problems , publisher = SIAM , year = 1976 , journal = SIAM Journal on Computing , volume = 5 , pages = 691–703 , url = http://link.aip.org/link/?SMJ/5/691/1 , doi = 10.1137/0205048 , issue = 4 , url-status = dead , archiveurl = https://archive.today/20130112133748/http://link.aip.org/link/?SMJ/5/691/1 , archivedate = 2013-01-12 ] For fractional flows, it is solvable in
polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
, as one can formulate the problem as a
linear program
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...
.
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 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
The minimum-cost flow problem (MCFP) is an optimization and decision problem to find the cheapest possible way of sending a certain amount of flow through a flow network. A typical application of this problem involves finding the best delivery rou ...
- As above, with 1 commodity.
*
Maximum flow problem
In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate.
The maximum flow problem can be seen as a special case of more complex network flow problems, such ...
- 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
Network flow problem
Mathematical problems