Polyhedral Investigation and Branch-and-Cut Algorithm for the Spectrum Assignment Problem
Diarrassouba, Ibrahima; Hadhbi, Youssouf; Mahjoub, Ali Ridha (2022), Polyhedral Investigation and Branch-and-Cut Algorithm for the Spectrum Assignment Problem, 23ème congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2022), Société Française de Recherche Opérationnelle et d’Aide à la Décision (ROADEF)
Type
Communication / ConférenceExternal document link
https://hal.archives-ouvertes.fr/hal-03595381/documentDate
2022Conference date
2022Conference country
FRANCEBook title
23ème congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2022)Publisher
Société Française de Recherche Opérationnelle et d’Aide à la Décision (ROADEF)
Metadata
Show full item recordAbstract (EN)
In this work we focus on the Spectrum Assignment (SA) problem related to the dimensioning and designing of Spectrally Flexible Optical Networks (SFONs). The SA is well known to be NP-hard problem [1]. It is equivalent to the problems of wavelength assignment, interval coloring, and dynamic storage allocation [1] 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. The main aim of our work is to provide a deep polyhedral investigation and design a cutting plane method for the problem. 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 their separation problems. Based on these results, we devise a Branch-and-Cut (B&C) algorithm for the problem.Subjects / Keywords
Network design, Routing, Spectrum assignment, Integer programming, Polyhedron, Facet, Valid inequalities, Symmetry, Breaking, Separation, Branch-and-cut, Primal heuristicRelated items
Showing items related by title and author.
-
Diarrassouba, Ibrahima; Hadhbi, Youssouf; Mahjoub, Ali Ridha (2021) Document de travail / Working paper
-
Diarrassouba, Ibrahima; Hadhbi, Youssouf; Mahjoub, Ali Ridha (2022) Communication / Conférence
-
Diarrassouba, Ibrahima; Mahjoub, Meriem; Mahjoub, Ali Ridha; Taktak, Raouia (2016) 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é
-
Diarrassouba, Ibrahima; Hadhbi, Youssouf; Mahjoub, Ali Ridha (2021) Document de travail / Working paper