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 its demand. The variable defines the fraction of flow along edge , where in case the flow can be split among multiple paths, and otherwise (i.e. "single path routing"). Find an assignment of all flow variables which satisfies the following four constraints:
(1) Link capacity: The sum of all flows routed over a link does not exceed its capacity.
(2) Flow conservation on transit nodes: The amount of a flow entering an intermediate node is the same that exits the node.
(3) Flow conservation at the source: A flow must exit its source node completely.
(4) Flow conservation at the destination: A flow must enter its sink node completely.
Corresponding optimization problems[]
Load balancing is the attempt to route flows such that the utilization of all links is even, where
The problem can be solved e.g. by minimizing . A common linearization of this problem is the minimization of the maximum utilization , where
In the minimum cost multi-commodity flow problem, there is a cost for sending a flow on . You then need to minimize
In the maximum multi-commodity flow problem, the demand of each commodity is not fixed, and the total throughput is maximized by maximizing the sum of all demands
Relation to other problems[]
The minimum cost variant of the multi-commodity flow problem is a generalization of the minimum cost flow problem (in which there is merely one source and one sink . Variants of the circulation problem are generalizations of all flow problems. That is, any flow problem can be viewed as a particular circulation problem.[1]
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,[2] 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,[3] or through (typically much faster) fully polynomial time approximation schemes.[4]
External resources[]
- Papers by Clifford Stein about this problem: http://www.columbia.edu/~cs2035/papers/#mcf
- Software solving the problem: https://web.archive.org/web/20130306031532/http://typo.zib.de/opt-long_projects/Software/Mcf/
References[]
- ^ Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Network Flows. Theory, Algorithms, and Applications. Prentice Hall.
- ^ 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.Even, S.; Itai, A.; Shamir, A. (1975). "On the complexity of time table and multi-commodity flow problems". 16th Annual Symposium on Foundations of Computer Science (SFCS 1975). pp. 184–193. doi:10.1109/SFCS.1975.21.
- ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2009). "29". Introduction to Algorithms (3rd ed.). MIT Press and McGraw–Hill. p. 862. ISBN 978-0-262-03384-8.CS1 maint: multiple names: authors list (link)
- ^ 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.
Add: Jean-Patrice Netter, Flow Augmenting Meshings: a primal type of approach to the maximum integer flow in a muti-commodity network, Ph.D dissertation Johns Hopkins University, 1971
- Network flow problem