Login | Register

Advanced Column Generation Decompositions for Optimizing Provisioning Problems in Optical Networks


Advanced Column Generation Decompositions for Optimizing Provisioning Problems in Optical Networks

Enoch, Julian (2018) Advanced Column Generation Decompositions for Optimizing Provisioning Problems in Optical Networks. Masters thesis, Concordia University.

Text (application/pdf)
MScCompSc_thesis_Julian_Enoch.pdf - Accepted Version
Restricted to Repository staff only until 1 July 2020.
Available under License Spectrum Terms of Access.


With the continued growth of Internet traffic, and the scarcity of the optical spectrum, there is a continuous need to optimize the usage of this resource. In the process of provisioning optical networks, telecommunication operators must deal with combinatorial optimization problems that are NP-complete. One of these problems is the Routing and Wavelength Allocation (RWA) which considers the fixed frequency grid, and the Routing and Spectrum Allocation (RSA) which is defined for the flexible frequency grid. While the flexible frequency grid paradigm attempted to improve the spectrum usage, the RSA problem has an additional spectrum dimension that makes it harder than the RWA problem.
In this thesis, in continuation of the previous studies, and using the advanced techniques of Integer Linear Programing, we propose a Column Generation algorithm based on a Lightpath decomposition which we implement for both the RWA and the RSA problems. This algorithm proved to be the most efficient so far producing optimal or near optimal solutions, and improving the computation times by two orders of magnitude on average. This algorithm is based on the approach of finding the right decomposition scheme as to be able to solve the Pricing Problem in a polynomial time. This approach can be used in other optimization problems.
In addition, we consider the same Configuration decomposition as the previous studies, and we propose an algorithm based on Nested Column Generation. We implemented this algorithm for both the RSA and the RWA problems, which led to a considerable improvement on the previous algorithms that use the same Configuration decomposition. This Nested Column Generation approach can be adopted in other optimization problems.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Enoch, Julian
Institution:Concordia University
Degree Name:M. Sc.
Program:Computer Science
Date:19 June 2018
Thesis Supervisor(s):Assi, Chadi and Jaumard, Brigitte
Keywords:WDM; Elastic Optical Networks; Routing and Wavelength Assignment; Routing and Spectrum Assignment; Integer Linear Programming; Decomposition Techniques; Column Generation; Nested Column Generation.
ID Code:983964
Deposited By: Julian Enoch
Deposited On:16 Nov 2018 16:37
Last Modified:27 Mar 2019 21:44
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Back to top Back to top