Discrete Location Problems Benchmarks Library


Text in pdffile 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_{1},...,P_{r} are paths from s to t, then a sum of pathflows along P_{1},...,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_{1},...,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_{1}, f_{2},..., f_{k} are flows of k commodities, then F = (f_{1}, f_{2},...,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 ∑_{i}  f_{i} , so that the sum of flows on any edge e ∈ E does not exceed u(e) and  f_{i}  ≤ d_{i}, i=1,...,k. The LengthBounded Maximum Multicommodity Flow with Unit EdgeLengths (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 timeexpanded 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,...,L1. A multicommodity flow is sought in this timeexpanded 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,...,L1 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'.
[1] T.C. Hu, Integer Programming and Network Flows, AddisonWesley 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 2044.