Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Valid Inequalities and Branch-and-Cut-and-Price Algorithm for the Constrained-Routing and Spectrum Assignment Problem

Abstract : 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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Youssouf Hadhbi Connect in order to contact the contributor
Submitted on : Thursday, July 15, 2021 - 2:47:07 PM
Last modification on : Thursday, October 21, 2021 - 3:33:40 AM
Long-term archiving on: : Saturday, October 16, 2021 - 6:40:13 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License


  • HAL Id : hal-03287242, version 1


Ibrahima Diarrassouba, Youssouf Hadhbi, Ali Ridha Mahjoub. Valid Inequalities and Branch-and-Cut-and-Price Algorithm for the Constrained-Routing and Spectrum Assignment Problem. 2021. ⟨hal-03287242⟩



Record views


Files downloads