Solving Large Instances of the RSA Problem in Flexgrid Elastic Optical Networks

Mirosław Klinkowski , Mateusz Żotkiewicz , Krzysztof Walkowiak , Michał Pióro , Marc Ruiz , Luis Velasco


We present an optimization procedure that mixes advanced large-scale optimization methods and heuristics to solve large instances (with over 1.7 million integer variables) of the routing and spectrum allocation (RSA) problem—a basic optimization problem in flexgrid elastic optical networks. We formulate the problem as a mixed-integer program for which we develop a branch-and-price algorithm enhanced with such techniques as problem relaxations and cuts for improving lower bounds (LBs) for the optimal objective value, and an RSA heuristic for improving the upper bounds. All these elements are combined into an effective optimization procedure. The results of numerical experiments run on network topologies of different dimensions and with large demand sets show that the algorithm performs well and can be applied to the problem instances that are difficult to solve using commercial solvers such as CPLEX.
Author Mirosław Klinkowski - [Instytut Łączności PIB (IŁ PIB)]
Mirosław Klinkowski,,
- Instytut Łączności PIB
, Mateusz Żotkiewicz (FEIT / IT)
Mateusz Żotkiewicz,,
- The Institute of Telecommunications
, Krzysztof Walkowiak - [Wydział Elektroniki [Wroclaw University of Science and Technology (PWr)]]
Krzysztof Walkowiak,,
- Wydział Elektroniki
, Michał Pióro (FEIT / IT)
Michał Pióro,,
- The Institute of Telecommunications
, Marc Ruiz - [Polytechnic University of Catalonia (UPC)]
Marc Ruiz,,
- Universitat Politècnica de Catalunya
, Luis Velasco - [Polytechnic University of Catalonia (UPC)]
Luis Velasco,,
- Universitat Politècnica de Catalunya
Journal seriesJournal of Optical Communications and Networking, ISSN 1943-0620
Issue year2016
Publication size in sheets0.5
Keywords in EnglishBranch and price; Cuts; Elastic optical networks; Large-scale optimization; Mixed-integer programming; Relaxations; Routing and Spectrum allocation
ASJC Classification1705 Computer Networks and Communications
ProjectIndustry-Driven Elastic and Adaptive Lambda Infrastructure for Service and Transport Networks . Project leader: Pióro Michał, , Phone: +48 22 234-7383, start date 01-11-2012, end date 31-10-2015, IT/2012/7PR/11, Completed
WEiTI 7 Framework Programme (7 FP) [7 Program Ramowy (7 PR)]
LTCC - Logical tunnel capacity control - a traffic routing and protection strategy for communication networks with variable link capacity. Project leader: Pióro Michał, , Phone: +48 22 234-7383, application date 10-06-2015, start date 24-02-2016, planned end date 20-12-2019, IT/2016/badawczy/46, Implemented
WEiTI Projects financed by NSC [Projekty finansowane przez NCN]
The Develpment of Digital Communicatios. Project leader: Siuzdak Jerzy, , Phone: +48 22 234-7868, start date 27-04-2015, end date 31-12-2016, IT/2015/statut, Completed
WEiTI Działalność statutowa
Languageen angielski
2016 Klinkowski żotkiewicz Pióro Solving Large Instances.pdf 447.25 KB
Score (nominal)35
Score sourcejournalList
ScoreMinisterial score = 30.0, 17-03-2020, ArticleFromJournal
Ministerial score (2013-2016) = 35.0, 17-03-2020, ArticleFromJournal
Publication indicators WoS Citations = 14; Scopus Citations = 18; GS Citations = 26.0; Scopus SNIP (Source Normalised Impact per Paper): 2016 = 1.351; WoS Impact Factor: 2016 = 2.261 (2) - 2016=2.283 (5)
Citation count*30 (2020-09-15)
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?