# Multi-commodity flow problem

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 ${\displaystyle \,G(V,E)}$, where edge ${\displaystyle (u,v)\in E}$ has capacity ${\displaystyle \,c(u,v)}$. There are ${\displaystyle \,k}$ commodities ${\displaystyle K_{1},K_{2},\dots ,K_{k}}$, defined by ${\displaystyle \,K_{i}=(s_{i},t_{i},d_{i})}$, where ${\displaystyle \,s_{i}}$ and ${\displaystyle \,t_{i}}$ is the source and sink of commodity ${\displaystyle \,i}$, and ${\displaystyle \,d_{i}}$ is its demand. The variable ${\displaystyle \,f_{i}(u,v)}$ defines the fraction of flow ${\displaystyle \,i}$ along edge ${\displaystyle \,(u,v)}$, where ${\displaystyle \,f_{i}(u,v)\in [0,1]}$ in case the flow can be split among multiple paths, and ${\displaystyle \,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.

${\displaystyle \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 ${\displaystyle u}$ is the same that exits the node.

${\displaystyle \forall i\in \{1,\ldots ,k\}:\,\sum _{w\in V}f_{i}(u,w)-\sum _{w\in V}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.

${\displaystyle \forall i\in \{1,\ldots ,k\}:\,\sum _{w\in V}f_{i}(s_{i},w)-\sum _{w\in V}f_{i}(w,s_{i})=1}$

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

${\displaystyle \forall i\in \{1,\ldots ,k\}:\,\sum _{w\in V}f_{i}(w,t_{i})-\sum _{w\in V}f_{i}(t_{i},w)=1}$

## Corresponding optimization problems

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

${\displaystyle 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 ${\displaystyle \sum _{u,v\in V}(U(u,v))^{2}}$. A common linearization of this problem is the minimization of the maximum utilization ${\displaystyle U_{max}}$, where

${\displaystyle \forall (u,v)\in E:\,U_{max}\geq U(u,v)}$

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

${\displaystyle \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 ${\displaystyle \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 ${\displaystyle s}$ and one sink ${\displaystyle 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

Routing and wavelength assignment (RWA) in optical burst switching of Optical Network would be approached via multi-commodity flow formulas.

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

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

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

## References

1. ^ Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Network Flows. Theory, Algorithms, and Applications. Prentice Hall.
2. ^ Koes, David Ryan (2009). "Towards a more principled compiler: Register allocation and instruction selection revisited" (PhD). Carnegie Mellon University. S2CID 26416771.
3. ^ S. Even and A. Itai and A. Shamir (1976). "On the Complexity of Timetable and Multicommodity Flow Problems". SIAM Journal on Computing. SIAM. 5 (4): 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.
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)
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.
6. ^ Algorithmic Nuggets in Content Delivery sigcomm.org

Add: Jean-Patrice Netter, Flow Augmenting Meshings: a primal type of approach to the maximum integer flow in a muti-commodity network, Ph.D dissertation Johns Hopkins University, 1971