multi-commodity flow problem

Given a flow network $\backslash ,G(V,E)$, where edge $(u,v)\; \backslash in\; E$ has capacity $\backslash ,c(u,v)$. There are $\backslash ,k$ commodities $K\_1,K\_2,\backslash dots,K\_k$, defined by $\backslash ,K\_i=(s\_i,t\_i,d\_i)$, where $\backslash ,s\_i$ and $\backslash ,t\_i$ is the source and sink of commodity $\backslash ,i$, and $\backslash ,d\_i$ is its demand. The variable $\backslash ,f\_i(u,v)$ defines the fraction of flow $\backslash ,i$ along edge $\backslash ,(u,v)$, where $\backslash ,f\_i(u,v)\; \backslash in\; [0,1]$ in case the flow can be split among multiple paths, and $\backslash ,f\_i(u,v)\; \backslash in\; \backslash \{0,1\backslash \}$ 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.

:$\backslash forall\; (u,v)\backslash in\; E:\backslash ,\backslash sum\_\{i=1\}^\{k\}\; f\_i(u,v)\backslash cdot\; d\_i\; \backslash 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.

:$\backslash forall\; i\backslash in\backslash \{1,\backslash ldots,k\backslash \}:\backslash ,\backslash sum\_\{(u,w)\; \backslash in\; E\}\; f\_i(u,w)\; -\; \backslash sum\_\{(w,u)\; \backslash in\; E\}\; f\_i(w,u)\; =\; 0\; \backslash quad\; \backslash mathrm\{when\}\; \backslash quad\; u\; \backslash neq\; s\_i,\; t\_i$

(3) Flow conservation at the source: A flow must exit its source node completely.

:$\backslash forall\; i\backslash in\backslash \{1,\backslash ldots,k\backslash \}:\backslash ,\backslash sum\_\{(u,w)\; \backslash in\; E\}\; f\_i(s\_i,w)\; -\; \backslash sum\_\{(w,u)\; \backslash in\; E\}\; f\_i(w,s\_i)\; =\; 1$

(4) Flow conservation at the destination: A flow must enter its sink node completely.

:$\backslash forall\; i\backslash in\backslash \{1,\backslash ldots,k\backslash \}:\; \backslash ,\backslash sum\_\{(u,w)\; \backslash in\; E\}\; f\_i(w,t\_i)\; -\; \backslash sum\_\{(w,u)\; \backslash in\; E\}\; f\_i(t\_i,w)\; =\; 1$

Load balancing is the attempt to route flows such that the utilization $U(u,v)$ of all links $(u,v)\backslash in\; E$ is even, where

:$U(u,v)=\backslash frac\{\backslash sum\_\{i=1\}^\{k\}\; f\_i(u,v)\backslash cdot\; d\_i\}\{c(u,v)\}$

The problem can be solved e.g. by minimizing $\backslash sum\_\{u,v\backslash in\; V\}\; (U(u,v))^2$. A common linearization of this problem is the minimization of the maximum utilization $U\_\{max\}$, where

:$\backslash forall\; (u,v)\backslash in\; E:\backslash ,\; U\_\{max\}\; \backslash geq\; U(u,v)$

In the minimum cost multi-commodity flow problem, there is a cost $a(u,v)\; \backslash cdot\; f(u,v)$ for sending a flow on $\backslash ,(u,v)$. You then need to minimize

:$\backslash sum\_\{(u,v)\; \backslash in\; E\}\; \backslash left(\; a(u,v)\; \backslash sum\_\{i=1\}^\{k\}\; f\_i(u,v)\backslash cdot\; d\_i\; \backslash 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 $\backslash sum\_\{i=1\}^\{k\}\; d\_i$

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

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

In the decision version of problems, the problem of producing an integer flow satisfying all demands is NP-complete,{{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 }} 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,{{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 }} or through (typically much faster) fully polynomial time approximation schemes.{{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 }}

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

• 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/

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