Handbook of Optimization in Telecommunications M.G.C. Resende and P.M. Pardalos (Editors) Springer Science + Business Media, 2006.
Chapter 10
Multicommodity flow problems and decomposition in telecommunications networks
A. Lisser and Ph. Mahey
Abstract
The purpose of this chapter is to investigate multicommodity flow problems that appear in the network design and operation of modern broadband packet-switched networks. We present arc-node and arc-path models and analyze specialized formulations corresponding to hard to solve instances like the minimax congestion problem and the capacity assignment of data networks in the presence of failures. Decomposition methods are studied to cope with the coupling constraints which define interactions between commodities on critical arcs or the combinatorial choice between normal and spare capacities. We focus here mainly on continuous flow models with linear or convex costs.
Keywords: Multicommodity flow problems, network design, packet-switched networks, arc-node models, arc-path models, minimax congestion, capacity assignment, decomposition methods, continuous flow models.