Valid Inequalities and Branch-and-Cut-and-Price Algorithm for the Constrained-Routing and Spectrum Assignment Problem
Diarrassouba, Ibrahima; Hadhbi, Youssouf; Mahjoub, Ali Ridha (2021), Valid Inequalities and Branch-and-Cut-and-Price Algorithm for the Constrained-Routing and Spectrum Assignment Problem. https://basepub.dauphine.psl.eu/handle/123456789/22210
TypeDocument de travail / Working paper
Series titlePreprint Lamsade
MetadataShow full item record
Mahjoub, Ali Ridha
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)In this work, we focus on a complex variant of the so-called 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. It is well known to be NP-hard and can be stated as follows. Consider a spectrally flexible optical network as an undirected, loopless, and connected graph G, and an optical spectrum S of available contiguous frequency slots, and a multiset of traffic demands K. The C-RSA consists of assigning for each traffic demand k ∈ K a path in G and an interval of contiguous frequency slots in S subject to technological constraints while optimizing some linear objective function(s). The main aim of our work is to introduce a new extended integer linear programming based on the so-called path formulation for the C-RSA. This formulation has an exponential number of variables. A column generation algorithm is then used to solve its linear relaxation. To do so, we investigate the structure and properties of the associated pricing problem. We further identify several classes of valid inequalities for the associated polytope and devise their separation procedures. Based on this, we devise Branch-and-Price (B&P) and Branchand-Cut-and-Price (B&C&P) algorithms to solve the problem. We give at the end a detailed behavior study of these algorithms.
Subjects / KeywordsSpectrally flexible optical network; network design; constrained-routing; spectrum assignment; complexity; ILP; pre-processing; valid inequality; separation; column generation; branch-and-price algorithm; branch-and-cut-and-price algorithm; conflict-graph; threshold graph; interval graph; perfect graph; intersection graph; primal heuristic; metaheuristics; heuristic; greedy-algorithm; dynamic programming algorithm; branching rules
Showing items related by title and author.
Valid Inequalities and Branch-and-Cut Algorithm for the Constrained-Routing and Spectrum Assignment Problem Diarrassouba, Ibrahima; Hadhbi, Youssouf; Mahjoub, Ali Ridha (2021) Document de travail / Working paper
Diarrassouba, Ibrahima; Hadhbi, Youssouf; Mahjoub, Ali Ridha (2021) Document de travail / Working paper
Mahjoub, Meriem; Diarrassouba, Ibrahima; Mahjoub, Ali Ridha; Taktak, Raouia (2017) Article accepté pour publication ou publié
Mailfert, Jean; Mahjoub, Ali Ridha; Didi Biha, Mohamed; Ibrahima, Diarrassouba; Bendali, Fatiha (2010) Article accepté pour publication ou publié