Problème du Routage Contraint et Assignation Spectrale : Étude Polyédrale et Algorithmes

Pour faire face à une croissance continue de la demande de trafic liée à l'augmentation de la bande passante, les opérateurs de réseaux ont dû faire évoluer l'architecture de leurs réseaux. En conséquence, une nouvelle génération de réseau de transport optique flexible appelée "Spectrally Flexible Optical Networks" (SFONs) a été introduite en 2008 comme une technologie prometteuse en raison de sa flexibilité et de son efficacité par rapport à l'ancienne technologie connue sous le nom "Optical Wavelength Division Multiplexing (WDM)". Les SFONs ont suscité un intérêt intense de la part des laboratoires de recherche, ainsi que dans l'industrie.Nous étudions dans cette thèse l'un des problèmes clés lors de dimensionnement et planification des SFONs, le problème du routage contraint et assignation spectrale, connue sous le nom " Constrained-Routing and Spectrum Assignment " (CRSA) selon la terminologie anglaise. Il se compose de deux parties: le routage contraint (sélectionner pour chaque demande en trafic un chemin optique physique qui connecte sa source avec sa destination à travers le réseau sans dépasser une longueur maximale de chemin (en km) fixée pour chaque demande en trafic), et l'assignation d'un spectre (assigner à chaque demande en trafic un seul intervalle de "slot" consécutifs (contrainte de contiguïté) au long de son chemin du routage de sorte que le même intervalle de slots consécutifs doit être utilisé sur tous les liens qui appartiennent à son chemin optique physique (contrainte de continuité), et les intervalles de slots consécutifs alloués par un ensemble de demandes dont les chemins ne sont pas des liens disjoints dans le réseau ne peuvent pas partager aucun slot sur les liens partagés (contrainte de non-chevauchement), tout en optimisant une ou plusieurs fonctions objectives linéaires. Le problème CRSA est bien connu comme un problème NP-difficile et très difficile en pratique aussi que de nombreuses études de recherche ont été menées dans ce contexte depuis sa première apparition en 2010. Certains des algorithmes de résolution proposés dans la littérature sont basés sur des formulations mathématiques utilisant la programmation linéaire (mixte) en nombres entiers qui n'ont pas pu résoudre des instances de grande taille, ainsi que des heuristiques et métaheuristiques qui ne peuvent pas garantir l'optimalité de solutions. Il a été jugé approprié de proposer des nouveaux modèles mathématiques plus souples et efficaces en se basant sur la programmation linéaire en nombres entiers, de concevoir et de développer des algorithmes exacts qui pourraient offrir des améliorations prometteuses par rapport aux méthodes existantes. À notre connaissance, l'étude polyédrale n'a pas encore fait l'objet de recherches récentes pour ce problème.Nous fournissons donc une analyse théorique approfondie et concevons des algorithmes exacts de type coupes, branchements et génération de colonnes pour résoudre le problème CRSA en considérant des réseaux de taille réaliste. Pour ce faire, notre contribution consiste à introduire un programme linéaire en nombres entiers basée sur des coupes, où le nombre de variables n'augmente que de manière polynomiale avec la taille de l'instance traitée. En outre, nous étudions la structure polyédrale du polyèdre associé, et dérivons plusieurs classes d'inégalités valides. Nous donnons quelques conditions nécessaires et suffisantes pour que certaines inégalités valides soient des facettes pour le polyèdre associé. Nous élaborons ensuite des procédures de séparation pour ces inégalités valides. Ces inégalités sont ensuite utilisées dans la relaxation linéaire afin d'obtenir des bornes duales plus serrées. En se basant sur ça, nous développons un algorithme de coupes et branchements pour le problème CRSA. (...)In this thesis, we study a variant of the Routing and Spectrum Assignment problem (RSA), namely the Constrained-Routing and Spectrum Assignment (C-RSA). The C-RSA problem is a key issue when dimensioning and managing a new generation of optical networks, called spectrally flexible optical networks. The C-RSA can be stated as follows. Given an undirected, loopless, and connected graph G, an optical spectrum S of available contiguous frequency slots, and a multiset of traffic demands K between pairs of origins and destinations, the C-RSA consists of assigning for each traffic demand k ∈ K a path in G between its origin and destination, and an interval of contiguous frequency slots in S so that some technological constraints are satisfied, and some linear objective function is optimized. First, we propose an integer linear programming formulation for the C-RSA. We identify several families of validinequalities for the associated polytope. Some of these inequalities are obtained by using the so-called conflict graphs. Moreover, we prove that these inequalities are facet-defining for the associated polytope under some necessary and sufficient conditions. In addition, we develop separation algorithms for these inequalities. Using these results, we devise a Branch-and-Cut (B&C) algorithm for the problem, and discuss experimental results. A second part of the sis is devoted to an extended formulation for the C-RSA. A column generation algorithm is developed to solve its linear relaxation. We prove that the related pricing problem is equivalent to the so-called resource constrained shortest path problem, which is well known to be NP-hard. For this, we propose a pseudo-polynomial time based dynamic programming algorithm. Using this, we devise Branch-and-Price (B&P) and Branch-and-Cut-and-Price (B&C&P) algorithms to solve the problem. An extensive experimental study with comparisons between the different B&C, B&P, and B&C&P algorithms is also presented.Finally, we turn our attention to the Spectrum Assignment (SA) sub-problem. This has been shown to be equivalent of wavelength assignment, interval coloring, and dynamic storage allocation problems that are well known to be NP-hard. To the best of our knowledge, a polyhedral approach to the SA problem has not been considered before, even to its equivalent problems. For this, first, we propose an integer linear programming compact formulation and investigate the facial structure of the associated polytope. Moreover, we identify several classes of valid inequalities for the polytope and prove that these inequalities are facet-defining. We further discuss the related separation problems. Using this, we devise a Branch-and-Cut (B&C) algorithm for the SA problem, along with some computational results are presented