On the Facial Structure of the Constrained-Routing and Spectrum Assignment Polyhedron: Part II - Université Clermont Auvergne Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2021

On the Facial Structure of the Constrained-Routing and Spectrum Assignment Polyhedron: Part II

Résumé

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.
Fichier principal
Vignette du fichier
DHM_Polyhedral_Investigation_HAL_Rearch_Report_II.pdf (1008.64 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Licence

Paternité

Identifiants

  • HAL Id : hal-03287205 , version 1

Citer

Ibrahima Diarrassouba, Youssouf Hadhbi, Ali Ridha Mahjoub. On the Facial Structure of the Constrained-Routing and Spectrum Assignment Polyhedron: Part II. 2021. ⟨hal-03287205⟩
115 Consultations
92 Téléchargements

Partager

Gmail Facebook X LinkedIn More