Thumbnail

Designing optical multi-band networks : polyhedral analysis and algorithms

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

Benhamiche, Amal (2013), Designing optical multi-band networks : polyhedral analysis and algorithms, doctoral thesis prepared under the supervision of Mahjoub, Ali Ridha, Université Paris Dauphine, 257 p.

View/Open
Type
Thèse
Date
2013-12
Pages
257
Metadata
Show full item record
Author(s)
Benhamiche, Amal
Under the direction of
Mahjoub, Ali Ridha
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.
Subjects / Keywords
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