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

≈ 4 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.

Definition

Given a flow network \,G(V,E) , where edge (u,v) \in E has capacity \,c(u,v) . There are \,k commodities K_1,K_2,\dots,K_k , defined by \,K_i=(s_i,t_i,d_i) , where \,s_i and \,t_i is the source and sink of commodity \,i , and \,d_i is its demand. The variable \,f_i(u,v) defines the fraction of flow \,i along edge \,(u,v) , where \,f_i(u,v) \in [0,1] in case the flow can be split among multiple paths, and \,f_i(u,v) \in \{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. \forall (u,v)\in E:\,\sum_{i=1}^{k} f_i(u,v)\cdot d_i \leq 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. \forall i\in\{1,\ldots,k\}:\,\sum_{(u,w) \in E} f_i(u,w) - \sum_{(w,u) \in E} f_i(w,u) = 0 \quad \mathrm{when} \quad u \neq s_i, t_i (3) Flow conservation at the source: A flow must exit its source node completely. \forall i\in\{1,\ldots,k\}:\,\sum_{(s_i,w) \in E} f_i(s_i,w) - \sum_{(w,s_i) \in E} f_i(w,s_i) = 1 (4) Flow conservation at the destination: A flow must enter its sink node completely. \forall i\in\{1,\ldots,k\}: \,\sum_{(w,t_i) \in E} f_i(w,t_i) - \sum_{(t_i,w) \in E} f_i(t_i,w) = 1

Corresponding optimization problems

Load balancing is the attempt to route flows such that the utilization U(u,v) of all links (u,v)\in E is even, where U(u,v)=\frac{\sum_{i=1}^{k} f_i(u,v)\cdot d_i}{c(u,v)} The problem can be solved e.g. by minimizing \sum_{u,v\in V} (U(u,v))^2 . A common linearization of this problem is the minimization of the maximum utilization U_{max} , where \forall (u,v)\in E:\, U_{max} \geq U(u,v) In the minimum cost multi-commodity flow problem, there is a cost a(u,v) \cdot f(u,v) for sending a flow on \,(u,v) . You then need to minimize \sum_{(u,v) \in E} \left( a(u,v) \sum_{i=1}^{k} f_i(u,v)\cdot d_i \right) 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 \sum_{i=1}^{k} d_i

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

Usage

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.

Solutions

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). If fractional flows are allowed, the problem can be solved in polynomial time through linear programming, or through (typically much faster) fully polynomial time approximation schemes.

Applications

Multicommodity flow is applied in the overlay routing in content delivery.

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

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 1775058178.0 · 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

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.