Valid Inequalities and Branch-and-Cut-and-Price Algorithm for the Constrained-Routing and Spectrum Assignment Problem - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

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

(1) , (2) , (3)
1
2
3

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.
Fichier principal
Vignette du fichier
DHM_B&C&P_HAL_Research_Report.pdf (727.25 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03287242 , version 1 (15-07-2021)

Licence

Attribution - CC BY 4.0

Identifiers

  • HAL Id : hal-03287242 , version 1

Cite

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⟩
107 View
53 Download

Share

Gmail Facebook Twitter LinkedIn More