Nested Decomposition Approach to an Optical Network Design Problem
VANDERBECK, François
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
VANDERBECK, François
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
< Réduire
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Langue
en
Rapport
Ce document a été publié dans
2009p. 18
Résumé en anglais
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 ...Lire la suite >
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.< Réduire
Origine
Importé de halUnités de recherche