• 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

Designing optical multi-band networks : polyhedral analysis and algorithms

Conception de réseaux optiques multi-bandes : Analyse polyédrale et algorithmes

Thumbnail
View/Open
2013PA090075.pdf (1.991Mb)
Date
2013-12
Dewey
Informatique générale
Sujet
Réseaux optiques multi-Bandes; Conception; Polytopes; Facette; Algorithme de coupe-Et-Branchement; Algorithme de génération-De-Colonnes-Et-Branchement; Optical multi-Band networks; Design; Polytope; Facet; Branch-And-Cut algorithm; Branch-And-Price algorithm
URI
https://basepub.dauphine.fr/handle/123456789/14809
Collections
  • LAMSADE : Thèses
Metadata
Show full item record
Author
Benhamiche, Amal
Thesis supervisor
Mahjoub, Ali Ridha
Type
Thèse
Item number of pages
257
Abstract (FR)
Dans cette thèse, on s'intéresse à deux problèmes de conception de réseaux, utilisant la technologie OFDM multi-bandes. Le premier problème concerne la conception d'un réseau mono-couche avec contraintes spécifiques. Nous donnons une formulation en PLNE pour ce problème et étudions le polyèdre associé à sa restriction sur un arc. Nous introduisons deux familles d'inégalités valides définissant des facettes et développons un algorithme de coupes et branchements pour le problème. Nous étudions la variante multicouche du problème précédent et proposons plusieurs PLNE pour le modéliser. Nous identifions plusieurs familles de facettes et discutons des problèmes de séparation associés. Nous développons un algorithme de coupes et branchements utilisant l'ensemble des contraintes identifiées. Enfin, une formulation compacte et deux formulations basées sur des chemins sont proposées pour le problème. Nous présentons deux algorithmes de génération de colonnes et branchements pour le problème.
Abstract (EN)
In this thesis we consider two capacitated network design (CND) problems, using OFDM multi-band technology. The first problem is related to single-layer network design with specific requirements. We give an ILP formulation for this problem and study the polyhedra associated with its arc-set restriction. We describe two families of facet defining inequalities. We devise a Branch-and-Cut algorithm for the problem. Next, we investigate the multilayer version of CND using OFDM technology. We propose several ILP formulations and study the polyhedron associated with the first (cut) formulation. We identify several classes of facets and discuss the related separation problem. We devise a Branch-and-Cut algorithm embedding valid inequalities of both single-layer and multilayer problems. The second formulation is compact, and holds a polynomial number of constraints and variables. Two further path formulations are given which yield two efficient Branch-and-Price algorithms for the problem.

Related items

Showing items related by title, author, creator and subject.

  • Survavibility in Multilayer Networks : models and Polyhedra 

    Taktak, Raouia (2013-07) Thèse
  • Approches de résolution exacte et approchée en optimisation combinatoire multi-objectif, application au problème de l'arbre couvrant de poids minimal 

    Lacour, Renaud (2014-07) Thèse
  • Numerical Methods for Multi-Marginal Optimal Transportation 

    Nenna, Luca (2016-12) Thèse

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