Solving large instances of the RSA problem in flexgrid elastic optical networks
(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)
- author
- Klinkowski, Mirosław ; Zotkiewicz, Mateusz ; Walkowiak, Krzysztof ; Pióro, Michał LU ; Ruiz, Marc and Velasco, Luis
- organization
- publishing date
- 2016-05-01
- 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
- article number
- 7489961
- 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
- 2024-04-05 14:19:28
@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>}},
author = {{Klinkowski, Mirosław and Zotkiewicz, Mateusz and Walkowiak, Krzysztof and Pióro, Michał and Ruiz, Marc and Velasco, Luis}},
issn = {{1943-0620}},
keywords = {{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}},
doi = {{10.1364/JOCN.8.000320}},
volume = {{8}},
year = {{2016}},
}