• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

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

Thumbnail
Date
2014
Dewey
Recherche opérationnelle
Sujet
conception de réseaux; polytope; facettes; algorithme de Branch and Cut
Conference name
ROADEF - 15ème congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision
Conference date
02-2014
Conference city
Bordeaux
Conference country
France
URI
https://basepub.dauphine.fr/handle/123456789/21188
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Benhamiche, Amal
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Mahjoub, Ali Ridha
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Perrot, Nancy
Type
Communication / Conférence
Abstract (FR)
Nous 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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.