Column generation algorithm for RSA problems in flexgrid optical networks

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


Finding optimal routes and spectrum allocation in flexgrid optical networks, known as the RSA problem, is an important design problem in transport communication networks. The problem is NP -hard, and its intractability becomes profound when network instances with several tens of nodes and several hundreds of demands are to be solved to optimum. In order to deal with such instances, large-scale optimization methods need to be considered. In this work, we present a column (more precisely, path) generation-based method for the RSA problem. The method is capable of finding reasonable sets of lightpaths, avoiding large sets of precomputed paths, and leading to high-quality solutions. Numerical results illustrating effectiveness of the proposed method for obtaining solutions for large RSA problem instances are presented.
Author Marc Ruiz - [Universitat Politecnica de Catalunya]
Marc Ruiz,,
, Michał Pióro (FEIT / IT)
Michał Pióro,,
- The Institute of Telecommunications
, Mateusz Żotkiewicz (FEIT / IT)
Mateusz Żotkiewicz,,
- The Institute of Telecommunications
, Mirosław Klinkowski - [Instytut Łacznosci, Poland]
Mirosław Klinkowski,,
, Luis Velasco - [Universitat Politecnica de Catalunya]
Luis Velasco,,
Journal seriesPhotonic Network Communications, ISSN 1387-974X, [1572-8188]
Issue year2013
Keywords in EnglishInteger programming, Column generation, Routing and spectrum allocation, Flexgrid optical networks
ASJC Classification2208 Electrical and Electronic Engineering; 1705 Computer Networks and Communications; 1708 Hardware and Architecture; 3107 Atomic and Molecular Physics, and Optics; 1712 Software
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)]
Mixed-integer programming models for joint optimization of link capacity assignment, flow scheduling, and routing in fair multicommodity flow networks. Project leader: Pióro Michał, , Phone: +48 22 234-7383, application date 07-06-2011, start date 07-12-2011, end date 06-12-2014, IT/2012/badawczy/30, Completed
WEiTI Projects financed by NSC [Projekty finansowane przez NCN]
The Develpment of Digital Communicatios. Project leader: Lubacz Józef, , Phone: 22 234 65 31, start date 04-05-2012, planned end date 31-03-2013, end date 31-12-2013, IT/2012/statut, Completed
WEiTI Działalność statutowa
Languageen angielski
Ruiz Pioro Zotkiewicz Column generation algorithm 2013.pdf 578.4 KB
Score (nominal)15
Score sourcejournalList
ScoreMinisterial score = 15.0, 17-03-2020, ArticleFromJournal
Ministerial score (2013-2016) = 15.0, 17-03-2020, ArticleFromJournal
Publication indicators WoS Citations = 25; Scopus Citations = 33; GS Citations = 46.0; Scopus SNIP (Source Normalised Impact per Paper): 2014 = 0.692; WoS Impact Factor: 2013 = 0.75 (2) - 2013=0.535 (5)
Citation count*47 (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?