Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Column Generation Algorithm for RSA Problems in Flexgrid Optical Networks

Ruiz, Marc ; Pioro, Michal LU ; Żotkiewicz, Mateusz ; Klinkowski, Mirosław and Velasco, Luis (2013) In Photonic Network Communications 26(2-3). p.53-64
Abstract
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
; ; ; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
Photonic Network Communications
volume
26
issue
2-3
pages
53 - 64
publisher
Springer
external identifiers
  • scopus:84889094309
ISSN
1387-974X
DOI
10.1007/s11107-013-0408-0
language
English
LU publication?
yes
id
a8ded5c0-a687-4399-887d-4bc3815d8971 (old id 5275895)
date added to LUP
2016-04-01 11:06:05
date last changed
2022-01-26 05:22:03
@article{a8ded5c0-a687-4399-887d-4bc3815d8971,
  abstract     = {{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       = {{Ruiz, Marc and Pioro, Michal and Żotkiewicz, Mateusz and Klinkowski, Mirosław and Velasco, Luis}},
  issn         = {{1387-974X}},
  language     = {{eng}},
  number       = {{2-3}},
  pages        = {{53--64}},
  publisher    = {{Springer}},
  series       = {{Photonic Network Communications}},
  title        = {{Column Generation Algorithm for RSA Problems in Flexgrid Optical Networks}},
  url          = {{http://dx.doi.org/10.1007/s11107-013-0408-0}},
  doi          = {{10.1007/s11107-013-0408-0}},
  volume       = {{26}},
  year         = {{2013}},
}