# 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 the demand. The flow of commodity ${\displaystyle \,i}$ along edge ${\displaystyle \,(u,v)}$ is ${\displaystyle \,f_{i}(u,v)}$. Find an assignment of flow which satisfies the constraints:

 Capacity constraints: ${\displaystyle \,\sum _{i=1}^{k}f_{i}(u,v)\leq c(u,v)}$ Flow conservation: ${\displaystyle \,\sum _{w\in V}f_{i}(u,w)=0\quad \mathrm {when} \quad u\neq s_{i},t_{i}}$ ${\displaystyle \,\forall v,u,\,f_{i}(u,v)=-f_{i}(v,u)}$ Demand satisfaction: ${\displaystyle \,\sum _{w\in V}f_{i}(s_{i},w)=\sum _{w\in V}f_{i}(w,t_{i})=d_{i}}$

In the minimum cost multi-commodity flow problem, there is a cost ${\displaystyle a(u,v)\cdot f(u,v)}$ for sending 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)\right)}$

In the maximum multi-commodity flow problem, there are no hard demands on each commodity, but the total throughput is maximised:

${\displaystyle \sum _{i=1}^{k}\sum _{w\in V}f_{i}(s_{i},w)}$

In the maximum concurrent flow problem, the task is to maximise the minimal fraction of the flow of each commodity to its demand:

${\displaystyle \min _{1\leq i\leq k}{\frac {\sum _{w\in V}f_{i}(s_{i},w)}{d_{i}}}}$

## Relation to other problems

The minimum cost variant is a generalisation of the minimum cost flow problem. Variants of the circulation problem are generalisations of all flow problems.

## Usage

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

## Solutions

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

## References

1. ^ 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. Retrieved 2016-10-05.
2. ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001) [1990]. "29". Introduction to Algorithms (2nd ed.). MIT Press and McGraw–Hill. pp. 788–789. ISBN 0-262-03293-7.
3. ^ 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.