On the Facial Structure of the Constrained-Routing and Spectrum Assignment Polyhedron: Part II
Diarrassouba, Ibrahima; Hadhbi, Youssouf; Mahjoub, Ali Ridha (2021), On the Facial Structure of the Constrained-Routing and Spectrum Assignment Polyhedron: Part II. https://basepub.dauphine.psl.eu/handle/123456789/22207
TypeDocument de travail / Working paper
Series titlePreprint Lamsade
MetadataShow full item record
Mahjoub, Ali Ridha
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)The constrained-routing and spectrum assignment (C-RSA) problem is a key issue when dimensioning and designing an optical network. Given an optical network G and a multiset of traffic demand K, it aims at determining for each traffic demand k ∈ K a path and an interval of contiguous slots while satisfying technological constraints and optimizing some linear objective function(s). In this paper, we introduce an integer linear programming formulation based on the so-called cut formulation for the C-RSA problem. We describe several valid inequalities for the associated polytope, and further give necessary and sufficient conditions under which these inequalities are facet defining. Based on these results, we develop a branch-and-cut algorithm to solve the problem.
Subjects / KeywordsOptical networks; constrained-routing; spectrum assignment; integer linear programming; polyhedron; dimension; valid inequality; facet; separation; branch-and-cut
Showing items related by title and author.
Valid Inequalities and Branch-and-Cut Algorithm for the Constrained-Routing and Spectrum Assignment Problem Diarrassouba, Ibrahima; Hadhbi, Youssouf; Mahjoub, Ali Ridha (2021) Document de travail / Working paper
Diarrassouba, Ibrahima; Mahjoub, Meriem; Mahjoub, Ali Ridha; Yaman, Hande (2016) Article accepté pour publication ou publié