Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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

Abstract : 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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

https://hal.uca.fr/hal-03287205
Contributor : Youssouf Hadhbi <>
Submitted on : Thursday, July 15, 2021 - 2:37:05 PM
Last modification on : Tuesday, July 20, 2021 - 4:00:56 AM

File

DHM_Polyhedral_Investigation_H...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

  • HAL Id : hal-03287205, version 1

Citation

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

Share

Metrics

Record views

50

Files downloads

30