Multi-commodity flow problem

flow network problem with multiple commodities between different source and sink nodes

Uses your system voice; voice and rate in settings.

Q6934437Snapshot

≈ 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

Definition

edit edit source

Given 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 source

Load 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 source

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 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 source

Routing 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 source

In 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 source

Multicommodity flow is applied in the overlay routing in content delivery.[6]

External resources

edit edit source

References

edit edit source
  1. ^ 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
  2. ^ 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
  3. ^ 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
  4. ^ 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
  5. ^ 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
  6. ^ 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.

Provenance

snapshot multi-commodity-flow-problem-781700-123f39f1d6d08b4d · hash 123f39f1d6d08b4d1551944c1c3d86ee1fbfa30f78b928ac8c7b55059ff86503 · captured 2026-04-01 · not yet sealed in the ledger · verify the chain · version history

Cite this page as: encyclopegia.org, “Multi-commodity flow problem”, snapshot multi-commodity-flow-problem-781700-123f39f1d6d08b4d. https://encyclopegia.org/a/multi-commodity-flow-problem