Advanced

Solving large instances of the RSA problem in flexgrid elastic optical networks

Klinkowski, Mirosław; Zotkiewicz, Mateusz; Walkowiak, Krzysztof; Pióro, Michał LU ; Ruiz, Marc and Velasco, Luis (2016) In Journal of Optical Communications and Networking 8(5). p.320-330
Abstract

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... (More)

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.

(Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Branch and price, Cuts, Elastic optical networks, Large-scale optimization, Mixed-integer programming, Relaxations, Routing and Spectrum allocation
in
Journal of Optical Communications and Networking
volume
8
issue
5
pages
11 pages
publisher
Optical Society of America
external identifiers
  • scopus:84976532346
  • wos:000378539200005
ISSN
1943-0620
DOI
10.1364/JOCN.8.000320
language
English
LU publication?
yes
id
854a929a-1102-44ff-b7fa-4a09e4cead49
date added to LUP
2017-02-02 13:45:08
date last changed
2017-10-22 05:25:50
@article{854a929a-1102-44ff-b7fa-4a09e4cead49,
  abstract     = {<p>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.</p>},
  articleno    = {7489961},
  author       = {Klinkowski, Mirosław and Zotkiewicz, Mateusz and Walkowiak, Krzysztof and Pióro, Michał and Ruiz, Marc and Velasco, Luis},
  issn         = {1943-0620},
  keyword      = {Branch and price,Cuts,Elastic optical networks,Large-scale optimization,Mixed-integer programming,Relaxations,Routing and Spectrum allocation},
  language     = {eng},
  month        = {05},
  number       = {5},
  pages        = {320--330},
  publisher    = {Optical Society of America},
  series       = {Journal of Optical Communications and Networking},
  title        = {Solving large instances of the RSA problem in flexgrid elastic optical networks},
  url          = {http://dx.doi.org/10.1364/JOCN.8.000320},
  volume       = {8},
  year         = {2016},
}