Multi-commodity flow problem

Summary

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

Definition

edit

Given a flow network  , where edge   has capacity  . There are   commodities  , defined by  , where   and   is the source and sink of commodity  , and   is its demand. The variable   defines the fraction of flow   along edge  , where   in case the flow can be split among multiple paths, and   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.

 

(2) Flow conservation on transit nodes: The amount of a flow entering an intermediate node   is the same that exits the node.

 

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

 

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

 

Corresponding optimization problems

edit

Load balancing is the attempt to route flows such that the utilization   of all links   is even, where

 

The problem can be solved e.g. by minimizing  . A common linearization of this problem is the minimization of the maximum utilization  , where

 

In the minimum cost multi-commodity flow problem, there is a cost   for sending a flow on  . You then need to minimize

 

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  

Relation to other problems

edit

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   and one sink  ). 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

edit

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.[2]

Solutions

edit

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

edit

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

External resources

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

edit
  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. 5 (4). SIAM: 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 multi-commodity network, Ph.D dissertation Johns Hopkins University, 1971