The multi-commodity flow problem is a network flow problem with multiple commodities (flow demands) between different source and sink nodes.
Contents
Definition
Given a flow network
(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
(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
Load balancing is the attempt to route flows such that the utilization
The problem can be solved e.g. by minimizing
In the minimum cost multi-commodity flow problem, there is a cost
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
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, 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. Or through (typically much faster) fully polynomial time approximation schemes.