Discrete Location Problems ballred.gif (861 bytes) Benchmarks Library
line.jpg (1129 bytes)

Length-Bounded Maximum Multicommodity
Flow with Unit Edge-Lengths
          

ballred.gif (861 bytes)  Home Benchmarks Library  

ballred.gif (861 bytes)  Benchmarks

ballred.gif (861 bytes)  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 [2]. 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'.

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.