TY - GEN
T1 - The Constrained-Routing and Spectrum Assignment Problem
T2 - 8th International Conference on Control, Decision and Information Technologies, CoDIT 2022
AU - Diarrassouba, Ibrahima
AU - Hadhbi, Youssouf
AU - Mahjoub, Ali Ridha
N1 - Publisher Copyright:
© 2022 IEEE.
PY - 2022
Y1 - 2022
N2 - In this paper, we study the Constrained-Routing and Spectrum Assignment (C-RSA) problem. Consider an undirected, loopless, and connected graph {G}. Let {S} be an optical spectrum of available contiguous frequency slots, and {K} be a set of traffic demands. The C-RSA is to assign for each demand {k,in,K} a path in {G} between its origin-destination nodes, and an interval of contiguous frequency slots in {S} while respecting some technological constraints, and optimizing some linear objective function. First, we propose an extended integer linear programming formulation for the C-RSA. A column generation algorithm is developed to solve its linear relaxation. We also describe several valid inequalities for the polytope associated with this formulation, and address the related separation problems. Using these results, we derive a Branch-and-Cut-and-Price algorithm, along with computational results are presented using large-scale instances.
AB - In this paper, we study the Constrained-Routing and Spectrum Assignment (C-RSA) problem. Consider an undirected, loopless, and connected graph {G}. Let {S} be an optical spectrum of available contiguous frequency slots, and {K} be a set of traffic demands. The C-RSA is to assign for each demand {k,in,K} a path in {G} between its origin-destination nodes, and an interval of contiguous frequency slots in {S} while respecting some technological constraints, and optimizing some linear objective function. First, we propose an extended integer linear programming formulation for the C-RSA. A column generation algorithm is developed to solve its linear relaxation. We also describe several valid inequalities for the polytope associated with this formulation, and address the related separation problems. Using these results, we derive a Branch-and-Cut-and-Price algorithm, along with computational results are presented using large-scale instances.
KW - branch-and-cut-and-price
KW - column generation
KW - dynamic programming
KW - extended formulation
KW - integer programming
KW - Optical network design
KW - separation
KW - valid inequalities
UR - https://www.scopus.com/pages/publications/85134308372
U2 - 10.1109/CoDIT55151.2022.9803881
DO - 10.1109/CoDIT55151.2022.9803881
M3 - Conference contribution
AN - SCOPUS:85134308372
T3 - 2022 8th International Conference on Control, Decision and Information Technologies, CoDIT 2022
SP - 926
EP - 931
BT - 2022 8th International Conference on Control, Decision and Information Technologies, CoDIT 2022
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 17 May 2022 through 20 May 2022
ER -