Abstract (EN)

In this work we focus on the Spectrum Assignment (SA) problem related to the dimensioning and designing of Spectrally Flexible Optical Networks (SFONs). The SA is well known to be NP-hard problem [1]. It is equivalent to the problems of wavelength assignment, interval coloring, and dynamic storage allocation [1] that are well known to be NP-hard. To the best of our knowledge, a polyhedral approach to the SA problem has not been considered before, even to its equivalent problems. The main aim of our work is to provide a deep polyhedral investigation and design a cutting plane method for the problem. First, we propose an integer linear programming compact formulation and investigate the facial structure of the associated polytope. Moreover, we identify several classes of valid inequalities for the polytope and prove that these inequalities are facet-defining. We further discuss their separation problems. Based on these results, we devise a Branch-and-Cut (B&C) algorithm for the problem.