Discrete Location Problems Benchmarks Library Length-Bounded Maximum Multicommodity Flow with Unit Edge-Lengths Home Benchmarks Library Benchmarks GAMS-model

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 P1,...,Pr are paths from s to t, then a sum of path-flows along P1,...,Pr gives a network flow from s to t again. Given that , we will say that f is routed along the set of paths P1,...,Pr.

We will assume that flow fi of commodity i, i = 1,...,k has an origin siV and a destination tiV.   If f1, f2,..., fk are flows of k commodities, then F = (f1, f2,...,fk) 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 (si, ti, di) ∈ V × V × R+ of commodity i for i=1,...,k. The objective is to maximize ∑i | fi |, so that the sum of flows on any edge eE does not exceed u(e) and | fi | ≤ di, i=1,...,k.

The Length-Bounded Maximum Multicommodity Flow with Unit Edge-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 eE does not exceed u(e), |fi| ≤ di, 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 (si, ti) are unique, since otherwise the demands with identical pairs (si, ti) 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 . The node set V' contains a copy Vt 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 vtVt in time layer t to vertex wt+1Vt+1. Besides that, E' contains edges (vt, vt+1) for all vtVt, 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 (vt, wt+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 si1 of vertex si at level 1 and the destination is placed in the copy tiL of vertex ti at level L. The resulting LP formulation is as follows where variables xi(e') ≥ 0 give the amount of flow of commodity i over edge e'E'.

 T.C. Hu, Integer Programming and Network Flows, Addison-Wesley Publishing Company, Reading, MA, 1970.932.

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