
Valid Inequalities and Branch-and-Cut Algorithm for the Constrained-Routing and Spectrum Assignment Problem
Diarrassouba, Ibrahima; Hadhbi, Youssouf; Mahjoub, Ali Ridha (2021), Valid Inequalities and Branch-and-Cut Algorithm for the Constrained-Routing and Spectrum Assignment Problem. https://basepub.dauphine.psl.eu/handle/123456789/22209
Type
Document de travail / Working paperDate
2021Series title
Preprint LamsadePublished in
Paris
Metadata
Show full item recordAuthor(s)
Diarrassouba, IbrahimaLaboratoire de Mathématiques Appliquées du Havre [LMAH]
Hadhbi, Youssouf
Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes [LIMOS]
Mahjoub, Ali Ridha
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
The Constrained-Routing and Spectrum Assignment (C-RSA) problem arises in the dimensioning and management of a next-generation of optical transport networks, called Spectrally Flexible Optical Networks (SFONs). The C-RSA can be stated as follows. Given an SFONs as a graph G, and an optical spectrum S of available contiguous frequency slots, and a multiset of traffic demands K, it aims at determining for each demand k ∈ K a path in G and an interval of contiguous slots in S while satisfying technological constraints, and optimizing some linear objective function(s). To the best of our knowledge, a cuttingplane-based approach has not been yet considered for the problem. For that, the main aim of our work is to introduce an integer linear programming formulation and provide several classes of valid inequalities for the associated polyhedron. We further discuss their separation problems. Using the polyhedral results and the separation procedures, we devise a Branchand-Cut algorithm to solve the problem. We also present some computational results and show the effectiveness of our approach using real and some realistic network topologiesSubjects / Keywords
AlgorithmRelated items
Showing items related by title and author.
-
Diarrassouba, Ibrahima; Hadhbi, Youssouf; Mahjoub, Ali Ridha (2022) Communication / Conférence
-
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é