Multi-commodity flow problem explained

The multi-commodity flow problem is a network flow problem with multiple commodities (flow demands) between different source and sink nodes.

Definition

G(V,E) , where edge (u,v) \in E has capacity c(u,v) . There are k commodities K _{1,K} _{2,...,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 ^{k} _{i =1} f _{i(u,v) ⋅} 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 _{w} f _{i(u,w)} - \sum _{w} f _{i(w,u)} = 0 when u ≠ 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 _{w} f _{i(s} _{i,w)} - \sum _{w} 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} f _{i(w,t} _{i)} - \sum _{w} 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, whereU(u,v) = (\sum ^{k} _{i =1} f _{i(u,v) ⋅} d _{i})/(c(u,v))

The problem can be solved e.g. by minimizing

\sum _{u,v\in} (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) ⋅ f(u,v) for sending a flow on (u,v) . You then need to minimize \sum _{(u,v)} \left( a(u,v) \sum ^{k} _{i =1} f _{i(u,v) ⋅} 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 ^{k} _{i =1} 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.^[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

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

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

1. Book: Ahuja . Ravindra K. . Magnanti . Thomas L. . Orlin . James B. . Network Flows. Theory, Algorithms, and Applications . 1993 . Prentice Hall.
2. PhD . Koes . David Ryan . 2009 . "Towards a more principled compiler: Register allocation and instruction selection revisited" . Carnegie Mellon University . 26416771 .
3. S. Even and A. Itai and A. Shamir . On the Complexity of Timetable and Multicommodity Flow Problems . SIAM . 1976 . SIAM Journal on Computing . 5 . 691–703. 10.1137/0205048. 4. Book: 10.1109/SFCS.1975.21. On the complexity of time table and multi-commodity flow problems. 16th Annual Symposium on Foundations of Computer Science (SFCS 1975). 184–193. 1975. Even. S.. Itai. A.. Shamir. A.. 18449466 .
4. Book: . Introduction to Algorithms . 3rd . 2009 . MIT Press and McGraw–Hill . 862 . 29 . 978-0-262-03384-8. Introduction to Algorithms .
5. George Karakostas . Faster approximation schemes for fractional multicommodity flow problems . Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms . 2002 . 0-89871-513-X . 166–173 .
6. https://www.sigcomm.org/sites/default/files/ccr/papers/2015/July/0000000-0000009.pdf Algorithmic Nuggets in Content Delivery

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