Nested Decomposition Approach to an Optical Network Design Problem

Benoit Vignac 1 François Vanderbeck 1, 2 Brigitte Jaumard 3
2 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : We consider a telecommunication optical network design problem where traffic routing decisions imply the installation of expensive equipment at nodes. Customer requests come in the form of bandwidth reservations for a given origin destination pair. Capacity reservations are expressed as a multiple of nominal granularities. Each nominal granularity request must be single path rooted, with at most 2 optical hops. Grooming several requests on the same wavelength and multiplexing wavelengths in the same optical stream allows to pack more traffic. However, each adding or dropping of a request from a wavelength requires optical to electrical conversion for which a specific expensive equipment is needed. We deal with backbone optical network with relatively few nodes (around 20) but thousands of requests. We implement a nested decomposition approach doe this problem. We gather several requests into basic routing patterns; we then pack those into a wavelength; finally, we make a selection of such traffic to wavelength assignments that covers demands at the cheapest cost. The dynamic generation of basic routing patterns and wavelength assignments is driven by a column generation algorithm where pricing is done either heuristically or exactly. A rounding heuristic where the master LP is optimized, to optimality or not, by column generation provides primal solutions. This approach allows to find good heuristic solutions to large scale instances.
Type de document :
[Research Report] 2009, pp.18
Liste complète des métadonnées
Contributeur : François Vanderbeck <>
Soumis le : jeudi 10 septembre 2009 - 15:40:31
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12


  • HAL Id : inria-00415500, version 1



Benoit Vignac, François Vanderbeck, Brigitte Jaumard. Nested Decomposition Approach to an Optical Network Design Problem. [Research Report] 2009, pp.18. 〈inria-00415500〉



Consultations de la notice