This paper presents a comprehensive survey of models and algorithms for multicommodity capacitated network design problems, which are mostly encountered in telecommunications and transportation network planning. These problems are important not only due to the major relevance of their applications, but also because they pose considerable modeling and algorithmic challenges. We present a general arc-based model, describe useful alternative formulations and survey the literature on simplex-based cutting plane and Lagrangian relaxation approaches. We then focus on our own contributions that develop and compare several relaxation methods for a particular case of this model, the fixed-charge problem. These methods are based on Lagrangian relaxation and nondifferentiable optimization techniques, namely, the subgradient and bundle approaches. Our experimental results, while very encouraging, indicate that solving effciently these diffcult problems requires a judicious combination of cutting planes, Lagrangian relaxation methods and sophisticated heuristics. In addition, due to their inherent decomposition properties, these techniques can be adapted to parallel computing environments, which is highly desirable in order to solve realistically sized instances.
Multicommodity Capacitated Network Design
FRANGIONI, ANTONIO;
1999-01-01
Abstract
This paper presents a comprehensive survey of models and algorithms for multicommodity capacitated network design problems, which are mostly encountered in telecommunications and transportation network planning. These problems are important not only due to the major relevance of their applications, but also because they pose considerable modeling and algorithmic challenges. We present a general arc-based model, describe useful alternative formulations and survey the literature on simplex-based cutting plane and Lagrangian relaxation approaches. We then focus on our own contributions that develop and compare several relaxation methods for a particular case of this model, the fixed-charge problem. These methods are based on Lagrangian relaxation and nondifferentiable optimization techniques, namely, the subgradient and bundle approaches. Our experimental results, while very encouraging, indicate that solving effciently these diffcult problems requires a judicious combination of cutting planes, Lagrangian relaxation methods and sophisticated heuristics. In addition, due to their inherent decomposition properties, these techniques can be adapted to parallel computing environments, which is highly desirable in order to solve realistically sized instances.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
