Date
2013-12
Alternative titles
Conception de réseaux optiques multi-bandes : Analyse polyédrale et algorithmes
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
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.
