Skip to main navigation Skip to search Skip to main content

The Constrained-Routing and Spectrum Assignment Problem: Extended Formulation and Branch-and-Cut-and-Price Algorithm

  • Normandie Université
  • Université Clermont Auvergne
  • Université PSL

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publication2022 8th International Conference on Control, Decision and Information Technologies, CoDIT 2022
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages926-931
Number of pages6
ISBN (Electronic)9781665496070
DOIs
StatePublished - 2022
Externally publishedYes
Event8th International Conference on Control, Decision and Information Technologies, CoDIT 2022 - Istanbul, Turkey
Duration: 17 May 2022 → 20 May 2022

Publication series

Name2022 8th International Conference on Control, Decision and Information Technologies, CoDIT 2022

Conference

Conference8th International Conference on Control, Decision and Information Technologies, CoDIT 2022
Country/TerritoryTurkey
CityIstanbul
Period17/05/22 → 20/05/22

Keywords

  • branch-and-cut-and-price
  • column generation
  • dynamic programming
  • extended formulation
  • integer programming
  • Optical network design
  • separation
  • valid inequalities

Fingerprint

Dive into the research topics of 'The Constrained-Routing and Spectrum Assignment Problem: Extended Formulation and Branch-and-Cut-and-Price Algorithm'. Together they form a unique fingerprint.

Cite this