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.
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 . 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
In the decision version of problems, the problem of producing an integer flow satisfying all demands is NP-complete, even for only two commodities and unit capacities (making the problem strongly NP-complete in this case).
- 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/
- 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.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001) . "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.