---

Text in pdf-file mcf.pdf

A flow in a digraph G = (V, E) from origin vertex s ∊ V to destination vertex t ∊ V is a nonnegative function  f : E → R₊ such that for each node v ∊ V, v ≠ s, v ≠ t holds

and

is the amount of flow sent from s to t in f.

If P₁,..., P_r are paths from s to t, then a sum of path-flows along P₁,..., P_r gives a network flow from s to t again. Given that , we will say that f is routed along the set of paths P₁,..., P_r.

We will assume that flow f_i of commodity i, i = 1,..., k has an origin s_i ∈ V and a destination t_i ∈ V.   If f₁, f₂, ..., f_k are flows of k commodities, then F = (f₁, f₂, ..., f_k) is called a multicommodity flow in G.

An input instance of the maximum multicommodity flow (MCF) consists of a directed network G = (V,E), where |V| = n, E = m, an edge capacity function u : E → R₊ and a specification (s_i, t_i, d_i) ∈ V × V × R⁺ of commodity i for i=1,...,k. The objective is to maximize , so that the sum of flows on any edge e ∈ E does not exceed u(e) and | f_i | ≤ d_i, i=1,...,k.

Lengths (LBMCF1) has the same input, extended by an upper bound L ∈ Z⁺ and asks for a maximum MCF where the sum of flows on any e ∈ E does not exceed u(e), |f_i| ≤ d_i, i = 1,...,k, and the flow of each commodity is routed along a set of paths at most L edges long. Obviously, the maximum MCF may be considered a special case of LBMCF1, assuming L = n. W.l.o.g. we will assume that all pairs (s_i, t_i) are unique, since otherwise the demands with identical pairs (s_i, t_i) may be summed together in one demand.

An LP formulation of LBMCF1, involving O(Lkn+m) constraints and O(Lkm) variables, may be constructed using a multicommodity flow in a supplementary time-expanded network [2]. The node set V' contains a copy V_t of the node set V of graph G for every discrete time step t, t=1,...,L. For every directed edge (v, w) ∈ E there is an edge in E' from vertex v_t ∈ V_t in time layer t to vertex w_t+1 ∈ V_t+1. Besides that, E' contains edges (v_t, v_t+1) for all v_t ∈ V_t, t = 1,..., L–1. A multicommodity flow is sought in this time-expanded network under additional constraints which require that for each e =(v, w) ∈ E the sum of all flows traversing the edges (v_t, w_t+1), t = 1,..., L–1 is at most u(e). For all i = 1,..., k, the origin of commodity i is placed in the copy s_i1 of vertex s_i at level 1 and the destination is placed in the copy t_iL of vertex t_i at level L. The resulting LP formulation is as follows

 

where variables x_i(e') ≥ 0 give the amount of flow of commodity i over edge e' ∈ E'.

REFERENCES

[1] T.C. Hu, Integer Programming and Network Flows, Addison-Wesley Publishing Company, Reading, MA, 1970.–932.

[2] P. Kolman and C. Scheideler, Improved bounds for the unsplittable flow problem, J. Algor. 61 (1) (2006), pp 20--44.