Multi-commodity flow problem
The multi-commodity flow problem is a network flow problem with multiple commodities (flow demands) between different source and sink nodes.
Definition
Given a flow network , where edge has capacity . There are commodities , defined by , where and is the source and sink of commodity , and is the demand. The flow of commodity along edge is . The capacity (maximum flow) along edge is represented by . Find an assignment of flow which satisfies the constraints:
Capacity constraints: Flow conservation: Demand satisfaction:
In the minimum cost multi-commodity flow problem, there is a cost for sending flow on . You then need to minimize
In the maximum multi-commodity flow problem, there are no hard demands on each commodity, but the total throughput is maximised:
In the maximum concurrent flow problem, the task is to maximise the minimal fraction of the flow of each commodity to its demand:
Relation to other problems
The minimum cost variant is a generalisation of the minimum cost flow problem. Variants of the circulation problem are generalisations of all flow problems.
Usage
Routing and wavelength assignment (RWA) in optical burst switching of Optical Network would be approached via multi-commodity flow formulas.
Solutions
In the decision version of problems, the problem of producing an integer flow satisfying all demands is NP-complete,[1] even for only two commodities and unit capacities (making the problem strongly NP-complete in this case).
If fractional flows are allowed, the problem can be solved in polynomial time through linear programming.[2] Or through (typically much faster) fully polynomial time approximation schemes.[3]
External resources
- Papers by Clifford Stein about this problem: http://www.columbia.edu/~cs2035/papers/#mcf
- Software solving the problem: http://typo.zib.de/opt-long_projects/Software/Mcf/
References
- ↑ S. Even and A. Itai and A. Shamir (1976). "On the Complexity of Timetable and Multicommodity Flow Problems". SIAM Journal on Computing. SIAM. 5 (4): 691–703. doi:10.1137/0205048. Retrieved 2016-10-05.
- ↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001) [1990]. "29". Introduction to Algorithms (2nd ed.). MIT Press and McGraw–Hill. pp. 788–789. ISBN 0-262-03293-7.
- ↑ George Karakostas (2002). "Faster approximation schemes for fractional multicommodity flow problems". Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms. pp. 166–173. ISBN 0-89871-513-X.