Abstract:

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 valid inequalities 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. 

The second part of the thesis 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.

Keywords: optical network, network design, integer programming, polyhedron, valid inequality, facet, separation, branch-and-cut, column generation, branch-and-price, branch-and-cut-and-price, dynamic programming.

Le jury sera composé de :

M. Ali Ridha Mahjoub, Professeur à l’Université de Paris Dauphine, Co-Encadrant de thèse
M. Ibrahima Diarrassouba, Docteur et Maître de Conférences à l’Université de Le Havre Normandie,  Examinateur
M. Mourad Baïou, Professeur à l’Université de Clermont Auvergne, Examinateur et 
Mme. Nancy Perrot , Docteur et Chercheur à Orange Labs, Examinateur
M. Eduardo Uchoa, Professeur à l’Université de Federal Fluminense, Rapporteur
Mme. Hande Yaman, Professeur à l’Université de KU Leuven, Rapporteur