Doctoral thesis defense: Hai Anh Hoang

Speaker: Hai Anh Hoang

Supervisor: Dr. B. Jaumard
Examining Committee: Drs. H. Harutyunyan,, J. Opatrny, J. Zhang, D. Colle, S. Narayanswamy (Chair)
Title: Scalable Column Generation Models and Algorithms for Optical Network Planning Problems
Date: Friday, June 6, 2014
Time: 10:00 a.m.
Place: EV 3.309

Abstract

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. 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, failure design of dependent and independent p-cycles, 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 Method.

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.