Branch-and-cut-and-price algorithm for the constrained-routing and spectrum assignment problem

Ibrahima Diarrassouba (), Youssouf Hadhbi () and A. Ridha Mahjoub ()
Additional contact information
Ibrahima Diarrassouba: LMAH, FR CNRS 3335, Le Havre Normandie University
Youssouf Hadhbi: LIMOS, UMR CNRS 6158, Clermont Auvergne INP
A. Ridha Mahjoub: Kuwait University

Journal of Combinatorial Optimization, 2024, vol. 47, issue 4, No 3, 37 pages

Abstract: Abstract The Constrained-Routing and Spectrum Assignment (C-RSA) problem arises in the design of 5G telecommunication optical networks. Given an undirected, loopless, and connected graph G, an optical spectrum of available contiguous frequency slots $${\mathbb {S}}$$ S , and a set of traffic demands K, the C-RSA consists of assigning, to each traffic demand $$k\in K$$ k ∈ K , a path in G between its origin and destination, and a subset of contiguous frequency slots in $${\mathbb {S}}$$ S subject to certain technological constraints while optimizing some linear objective function. In this paper, we devise an exact algorithm to solve the C-RSA. We first introduce an extended integer programming formulation for the problem. Then we investigate the associated polytope and introduce several classes of valid inequalities. Based on these results, we devise a Branch-and-Cut-and-Price algorithm for the problem and present an extensive computational study. This is also be compared with a Branch-and-Cut algorithm of the state-of-the-art.

Keywords: 5G Network design; Branch-and-Cut-and-Price; Valid inequalities (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01125-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:47:y:2024:i:4:d:10.1007_s10878-024-01125-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01125-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().