Login | Register

Scalable Column Generation Models and Algorithms for Optical Network Planning Problems


Scalable Column Generation Models and Algorithms for Optical Network Planning Problems

Hoang, Hai Anh (2014) Scalable Column Generation Models and Algorithms for Optical Network Planning Problems. PhD thesis, Concordia University.

[thumbnail of Hoang_PhD_F2014.pdf]
Text (application/pdf)
Hoang_PhD_F2014.pdf - Accepted Version
Available under License Spectrum Terms of Access.


Column Generation Method has been proved to be a powerful tool to model and solve large scale optimization problems in various practical domains such as operation management, logistics and computer design. Such a decomposition approach has been also applied in telecommunication for several classes of classical network design and planning problems with a great success.

In this thesis, we confirm that Column Generation Methodology is also a powerful tool in solving several contemporary network design problems that come from a rising worldwide demand of heavy traffic (100Gbps, 400Gbps, and 1Tbps) with emphasis on cost-effective and resilient networks. Such problems are very challenging in terms of complexity as well as solution quality. Research in this thesis attacks four challenging design problems in optical networks: design of p-cycles subject to wavelength continuity, design of dependent and independent p-cycles against multiple failures, design of survivable virtual topologies against multiple failures, design of a multirate optical network architecture. For each design problem, we develop a new mathematical models based on Column Generation Decomposition scheme.

Numerical results show that Column Generation methodology is the right choice to deal with hard network design problems since it allows us to efficiently solve large scale network instances which have been puzzles for the current state of art. Additionally, the thesis reveals the great flexibility of Column Generation in formulating design problems that have quite different natures as well as requirements.

Obtained results in this thesis show that, firstly, the design of p-cycles should be under a wavelength continuity assumption in order to save the converter cost since the difference between the capacity requirement under wavelength conversion vs. under wavelength continuity is insignificant. Secondly, such results which come from our new general design model for failure dependent p-cycles prove the fact that failure dependent p-cycles save significantly spare capacity than failure independent p-cycles. Thirdly, large instances can be quasi-optimally solved in case of survivable topology designs thanks to our new path-formulation model with online generation of augmenting paths. Lastly, the importance of high capacity devices such as 100Gbps transceiver and the impact of the restriction on number of regeneration sites to the provisioning cost of multirate WDM networks are revealed through our new hierarchical Column Generation model.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (PhD)
Authors:Hoang, Hai Anh
Institution:Concordia University
Degree Name:Ph. D.
Program:Computer Science and Software Engineering
Date:20 August 2014
Thesis Supervisor(s):Jaumard, Brigitte
ID Code:978849
Deposited By: HAI ANH HOANG
Deposited On:20 Nov 2014 19:27
Last Modified:18 Jan 2018 17:47
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

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top