Multi-commodity flow problem
flow network problem with multiple commodities between different source and sink nodes
≈ 5 min read
Names in other languages
- FrançaisProblème de flot multi-commodités
- MagyarMulti-commodity flow probléma
- EnglishMulti-commodity flow problem
- 日本語多品種フロー問題多品種流問題
- 中文多物網絡流問題
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
The multi-commodity flow problem is a network flow problem with multiple commodities (flow demands) between different source and sink nodes.
Contents
- 1 Definition
- 2 Corresponding optimization problems
- 3 Relation to other problems
- 4 Usage
- 5 Solutions
- 6 Applications
- 7 External resources
- 8 References
Definition
edit edit sourceGiven a flow network G(V,E), where edge (u,v)∈E has capacity c(u,v). There are k commodities K1,K2,…,Kk, defined by Ki=(si,ti,di), where si and ti is the source and sink of commodity i, and di is its demand. The variable fi(u,v) defines the fraction of flow i along edge (u,v), where fi(u,v)∈[0,1] in case the flow can be split among multiple paths, and fi(u,v)∈{0,1} 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.
- ∀(u,v)∈E:∑i=1kfi(u,v)⋅di≤c(u,v)
(2) Flow conservation on transit nodes: The amount of a flow entering an intermediate node u is the same that exits the node.
- ∀i∈{1,…,k}:∑(u,w)∈Efi(u,w)−∑(w,u)∈Efi(w,u)=0whenu≠si,ti
(3) Flow conservation at the source: A flow must exit its source node completely.
- ∀i∈{1,…,k}:∑(si,w)∈Efi(si,w)−∑(w,si)∈Efi(w,si)=1
(4) Flow conservation at the destination: A flow must enter its sink node completely.
- ∀i∈{1,…,k}:∑(w,ti)∈Efi(w,ti)−∑(ti,w)∈Efi(ti,w)=1
Corresponding optimization problems
edit edit sourceLoad balancing is the attempt to route flows such that the utilization U(u,v) of all links (u,v)∈E is even, where
- U(u,v)=∑i=1kfi(u,v)⋅dic(u,v)
The problem can be solved e.g. by minimizing ∑u,v∈V(U(u,v))2. A common linearization of this problem is the minimization of the maximum utilization Umax, where
- ∀(u,v)∈E:Umax≥U(u,v)
In the minimum cost multi-commodity flow problem, there is a cost a(u,v)⋅f(u,v) for sending a flow on (u,v). You then need to minimize
- ∑(u,v)∈E(a(u,v)∑i=1kfi(u,v)⋅di)
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 ∑i=1kdi
Relation to other problems
edit edit sourceThe 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 s and one sink t). 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
edit edit sourceRouting and wavelength assignment (RWA) in optical burst switching of Optical Network would be approached via multi-commodity flow formulas, if the network is equipped with wavelength conversion at every node.
Register allocation can be modeled as an integer minimum cost multi-commodity flow problem: Values produced by instructions are source nodes, values consumed by instructions are sink nodes and registers as well as stack slots are edges.[2]
Solutions
edit edit sourceIn the decision version of problems, the problem of producing an integer flow satisfying all demands is NP-complete,[3] 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,[4] or through (typically much faster) fully polynomial time approximation schemes.[5]
Applications
edit edit sourceMulticommodity flow is applied in the overlay routing in content delivery.[6]
External resources
edit edit source- 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
edit edit source- ^ Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Network Flows. Theory, Algorithms, and Applications. Prentice Hall. Wikipedia revision 1346580435, retrieved 2026-11-20
- ^ Koes, David Ryan (2009). "Towards a more principled compiler: Register allocation and instruction selection revisited" (PhD). Carnegie Mellon University. S2CID 26416771. Wikipedia revision 1346580435, retrieved 2026-11-20
- ^ S. Even and A. Itai and A. Shamir (1976). "On the Complexity of Timetable and Multicommodity Flow Problems". SIAM Journal on Computing. 5 (4). SIAM: 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. S2CID 18449466. Wikipedia revision 1346580435, retrieved 2026-11-20
- ^ 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.
{{cite book}}: CS1 maint: multiple names: authors list (link) Wikipedia revision 1346580435, retrieved 2026-11-20 - ^ 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. Wikipedia revision 1346580435, retrieved 2026-11-20
- ^ Bruce M. Maggs and Ramesh K. Sitaraman (2015). "Algorithmic Nuggets in Content Delivery". ACM SIGCOMM Computer Communication Review. 45 (3). ACM: 52–66. doi:10.1145/2805789.2805800. Wikipedia revision 1346580435, retrieved 2026-11-20
Add: Jean-Patrice Netter, Flow Augmenting Meshings: a primal type of approach to the maximum integer flow in a multi-commodity network, Ph.D. dissertation Johns Hopkins University, 1971
Text derived from https://en.wikipedia.org/w/index.php?oldid=1346580435 under CC BY-SA 4.0; modifications have been made.