Show simple item record

Dimensionnement de réseaux optiques multi-bandes : Polyèdre et Branch-and-Cut

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorBenhamiche, Amal
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorMahjoub, Ali Ridha
hal.structure.identifier
dc.contributor.authorPerrot, Nancy
dc.date.accessioned2020-11-04T14:35:33Z
dc.date.available2020-11-04T14:35:33Z
dc.date.issued2014
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/21188
dc.description.abstractfrNous nous intéressons dans ce papier au problème de dimensionnement d'un réseau optique multicouche, utilisant la technologie OFDM (Orthogonal Frequency Division Multiplexing) Multi-Bandes. Etant donnée une couche physique de réseau composée d'un ensemble de noeuds de transmission, liés par des fibres optiques, et des demandes définies par une origine, une destination et une quantité de trafic. On dispose d'un ensemble de capacités modulaires, appelées sous-bandes OFDM, à installer entre les nœuds de transmission, de sorte que la circulation du trafic soit possible. Chaque sous-bande possède une capacité et induit un coût d'installation, qui est celui des équipements optiques qui génèrent la sous-bande. Si une ou plusieurs sous-bandes sont installées entre deux noeuds de transmission, on dit qu'il existe un lien virtuel entre ces noeuds. L'ensemble des liens virtuels ainsi que les noeuds extrémités définissent la couche virtuelle du réseau optique. Le problème que nous étudions peut alors être défini comme suit. Nous souhaitons déterminer le nombre de sous-bandes OFDM à installer sur les liens du réseau, de sorte que toute les demandes soient routées, que chaque sous-bande utilisée soit associée à un chemin utilisant des fibres optiques, et que le coût total soit minimum. Nous appellerons ce problème Conception de Réseau Optique Multi-Bandes (Optical Multi-Band Network Design (OMBND) problem).Nous proposons ici une approche de modélisation basée sur des coupes, et donnons une formulation en programme linéaire en nombres entiers ayant un nombre exponentiel de contraintes. Nous examinons d'abord le polyèdre associé à la formulation en coupes ainsi que la structure faciale des contraintes de base. Nous dérivons ensuite d'autres familles d'inégalités valides, et décrivons les conditions nécessaires aussi bien que les conditions suffisantes pour qu'elles définissent des facettes non triviales du polyèdre. Par ailleurs, nous proposons une étude expérimentale afin d'avoir un aperçu sur l'efficacité, en pratique, des contraintes valides introduites. Nous décrivons d'abord les procédures de séparation que nous proposons afin de générer chaque famille d'inégalités valides. Nous donnons ensuite les détails de la mise en œuvre et présentons les instances de réseaux considérées dans notre étude expérimentale. Enfin, des résultats numériques sont donnés pour des instances réalistes issues de la librairie SNDlib, ainsi que pour des instances réelles fournies par Orange Labs. Nos résultats montrent le gain apporté par les inégalités valides proposées comparé à la formulation de base. En particulier, les inégalités de type Min Set I, Capacitated Cutset inequalities et Flow-Cutset inequalities ont permis de réduire sensiblement le saut d'intégrité, et ainsi d'améliorer la qualité de la relaxation linéaire de la formulation en coupes.en
dc.language.isofren
dc.subjectconception de réseauxen
dc.subjectpolytopeen
dc.subjectfacettesen
dc.subjectalgorithme de Branch and Cuten
dc.subject.ddc003en
dc.titleDimensionnement de réseaux optiques multi-bandes : Polyèdre et Branch-and-Cuten
dc.typeCommunication / Conférence
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.conftitleROADEF - 15ème congrès annuel de la Société française de recherche opérationnelle et d'aide à la décisionen
dc.relation.confdate2014-02
dc.relation.confcityBordeauxen
dc.relation.confcountryFranceen
dc.relation.forthcomingnonen
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2020-11-04T14:33:36Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record