La plateforme OSKAR Bordeaux évolue pour rejoindre l'archive ouverte HAL. Retrouvez tous vos dépôts sur le nouveau portail HAL UB : https://u-bordeaux.hal.science/. Pour toute aide ou information, contactez-nous info@oskar-bordeaux.fr

Afficher la notice abrégée

Nested Decomposition Approach to an Optical Network Design Problem

hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
dc.contributor.authorVIGNAC, Benoit
hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorVANDERBECK, François
hal.structure.identifierConcordia Institute for Information Systems Engineering [CIISE]
dc.contributor.authorJAUMARD, Brigitte
dc.date.accessioned2024-04-04T02:33:43Z
dc.date.available2024-04-04T02:33:43Z
dc.date.created2009-09-09
dc.date.issued2009
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/190502
dc.description.abstractEnWe 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.
dc.language.isoen
dc.title.enNested Decomposition Approach to an Optical Network Design Problem
dc.typeRapport
bordeaux.page18
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.type.reportrr
hal.identifierinria-00415500
hal.version1
hal.audienceNon spécifiée
hal.origin.linkhttps://hal.archives-ouvertes.fr//inria-00415500v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2009&rft.spage=18&rft.epage=18&rft.au=VIGNAC,%20Benoit&VANDERBECK,%20Fran%C3%A7ois&JAUMARD,%20Brigitte&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée