173.178.173.191: /* Usage */

2024-11-19T22:53:49Z

Usage

New page

{{Short description|Network flow problem (mathematics)}}
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]] <math>\,G(V,E)</math>, where edge <math>(u,v) \in E</math> has capacity <math>\,c(u,v)</math>. There are <math>\,k</math> commodities <math>K_1,K_2,\dots,K_k</math>, defined by <math>\,K_i=(s_i,t_i,d_i)</math>, where <math>\,s_i</math> and <math>\,t_i</math> is the '''source''' and '''sink''' of commodity <math>\,i</math>, and <math>\,d_i</math> is its demand. The variable <math>\,f_i(u,v)</math> defines the fraction of flow <math>\,i</math> along edge <math>\,(u,v)</math>, where <math>\,f_i(u,v) \in [0,1]</math> in case the flow can be split among multiple paths, and <math>\,f_i(u,v) \in \{0,1\}</math> 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.
:<math>\forall (u,v)\in E:\,\sum_{i=1}^{k} f_i(u,v)\cdot d_i \leq c(u,v)</math>

'''(2) Flow conservation on transit nodes:''' The amount of a flow entering an intermediate node <math>u</math> is the same that exits the node.
:<math>\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 </math>

'''(3) Flow conservation at the source:''' A flow must exit its source node completely.
:<math>\forall i\in\{1,\ldots,k\}:\,\sum_{(u,w) \in E} f_i(s_i,w) - \sum_{(w,u) \in E} f_i(w,s_i) = 1</math>

'''(4) Flow conservation at the destination:''' A flow must enter its sink node completely.
:<math>\forall i\in\{1,\ldots,k\}: \,\sum_{(u,w) \in E} f_i(w,t_i) - \sum_{(w,u) \in E} f_i(t_i,w) = 1</math>

==Corresponding optimization problems==

'''Load balancing''' is the attempt to route flows such that the utilization <math>U(u,v)</math> of all links <math>(u,v)\in E</math> is even, where

:<math>U(u,v)=\frac{\sum_{i=1}^{k} f_i(u,v)\cdot d_i}{c(u,v)}</math>

The problem can be solved e.g. by minimizing <math>\sum_{u,v\in V} (U(u,v))^2</math>. A common linearization of this problem is the minimization of the maximum utilization <math>U_{max}</math>, where

:<math>\forall (u,v)\in E:\, U_{max} \geq U(u,v)</math>

In the '''minimum cost multi-commodity flow problem''', there is a cost <math>a(u,v) \cdot f(u,v)</math> for sending a flow on <math>\,(u,v)</math>. You then need to minimize

:<math>\sum_{(u,v) \in E} \left( a(u,v) \sum_{i=1}^{k} f_i(u,v)\cdot d_i \right)</math>

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 <math>\sum_{i=1}^{k} d_i</math>

==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 <math>s</math> and one sink <math>t</math>). Variants of the [[circulation problem]] are generalizations of all flow problems. That is, any flow problem can be viewed as a particular circulation problem.<ref name="ahuja_et_al_1993">{{cite book |last1=Ahuja |first1=Ravindra K. |last2=Magnanti |first2=Thomas L. |last3=Orlin |first3=James B. |title=Network Flows. Theory, Algorithms, and Applications |date=1993 |publisher=Prentice Hall}}</ref>

==Usage==

[[Routing and wavelength assignment]] (RWA) in [[optical burst switching]] of [[SONET|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.<ref>{{cite thesis |type=PhD |last=Koes |first=David Ryan |date=2009 |title="Towards a more principled compiler: Register allocation and instruction selection revisited" |publisher=Carnegie Mellon University |s2cid=26416771 }}</ref>

==Solutions==

In the decision version of problems, the problem of producing an integer flow satisfying all demands is [[NP-complete]],<ref name="EIS76">{{cite journal | author = S. Even and A. Itai and A. Shamir | title = On the Complexity of Timetable and Multicommodity Flow Problems | publisher = SIAM | year = 1976 | journal = SIAM Journal on Computing | volume = 5 | pages = 691–703| doi = 10.1137/0205048| issue = 4}}{{Cite book|doi=10.1109/SFCS.1975.21|chapter=On the complexity of time table and multi-commodity flow problems|title=16th Annual Symposium on Foundations of Computer Science (SFCS 1975)|pages=184–193|year=1975|last1=Even|first1=S.|last2=Itai|first2=A.|last3=Shamir|first3=A.|s2cid=18449466 }}</ref> 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]],<ref>{{cite book | author = [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]] | title = Introduction to Algorithms | edition = 3rd | year = 2009 | publisher = MIT Press and McGraw–Hill | pages = 862 | chapter = 29 | isbn = 978-0-262-03384-8| title-link = Introduction to Algorithms }}</ref> or through (typically much faster) [[fully polynomial time approximation scheme]]s.<ref>{{cite conference | author = George Karakostas | title = Faster approximation schemes for fractional multicommodity flow problems | book-title = Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms | year = 2002 | isbn = 0-89871-513-X | pages = [https://archive.org/details/proceedingsofthi2002acms/page/166 166–173] | url = https://archive.org/details/proceedingsofthi2002acms/page/166 }}</ref>



==Applications==
Multicommodity flow is applied in the overlay routing in content delivery.<ref>[https://www.sigcomm.org/sites/default/files/ccr/papers/2015/July/0000000-0000009.pdf Algorithmic Nuggets in Content Delivery] sigcomm.org</ref>

==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==
<references/>

{{DEFAULTSORT:Multi-Commodity Flow Problem}}
[[Category:Network flow problem]]
[[Category:NP-complete problems]]

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

Multi-commodity flow problem - Revision history

173.178.173.191: /* Usage */