Skip to Main content Skip to Navigation
Conference papers

A novel integer linear programming model for routing and spectrum assignment in optical networks

Abstract : The routing and spectrum assignment problem is an NP-hard problem that receives increasing attention during the last years. Existing integer linear programming models for the problem are either very complex and suer from tractability issues or are simplied and incomplete so that they can optimize only some objective functions. The majority of models uses edge-path formulations where variables are associated with all possible routing paths so that the number of variables grows exponentially with the size of the instance. An alternative is to use edge-node formulations that allow to devise compact models where the number of variables grows only polynomially with the size of the instance. However, all known edge-node formulations are incomplete as their feasible region is a superset of all feasible solutions of the problem and can, thus, handle only some objective functions. Our contribution is to provide the rst complete edge-node formulation for the routing and spectrum assignment problem which leads to a tractable integer linear programming model. Indeed, computational results show that our complete model is competitive with incomplete models as we can solve instances of the RSA problem larger than instances known in the literature to optimality within reasonable time and w.r.t. several objective functions. We further devise some directions of future research.
Document type :
Conference papers
Complete list of metadata

https://hal.uca.fr/hal-03135240
Contributor : Annegret Wagler <>
Submitted on : Monday, February 8, 2021 - 6:57:28 PM
Last modification on : Wednesday, February 24, 2021 - 4:24:03 PM
Long-term archiving on: : Sunday, May 9, 2021 - 8:32:37 PM

File

HKW_ENF_Lpz2019_HAL.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Youssouf Hadhbi, Hervé Kerivin, Annegret Wagler. A novel integer linear programming model for routing and spectrum assignment in optical networks. 2019 Federated Conference on Computer Science and Information Systems, Sep 2019, Leipzig, Germany. pp.127-134, ⟨10.15439/2019F188⟩. ⟨hal-03135240⟩

Share

Metrics

Record views

56

Files downloads

32