Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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.
Document type :
Reports (Research report)
Complete list of metadata
Contributor : François Vanderbeck Connect in order to contact the contributor
Submitted on : Thursday, September 10, 2009 - 3:40:31 PM
Last modification on : Wednesday, October 26, 2022 - 8:16:25 AM


  • 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⟩



Record views