Large-Scale Modeling and Optimization of Routing, Modulation and Spectrum Assignment Problems in Optical Networks

One of the crucial decisions in managing flexible optical fiber networks is the provisioning of connection requests, known as the Routing and Spectrum Assignment (RSA) problem, and its extension: Routing, Modulation and Spectrum Assignment (RMSA) problem. Such problems are becoming more and more challenging everyday with the steadily increasing demand in optical networking. Therefore, considerable research effort has been exerted in developing models and algorithms to efficiently solve larger problem instances. Yet, there still exists a gap between the problem sizes that can be solved thanks to the previous research efforts and the realistic problem sizes. This work is one step forward towards reducing this gap. In this thesis, we propose decomposition models for the RSA and RMSA problems based on lightpath configurations. The proposed models are Integer Linear Programs (ILPs) with an exponential number of configuration variables. Therefore, we have developed nested column generation algorithms to exactly solve both problems. Furthermore, Lagrangian Relaxation is used to compute valid upper bounds on the Integer Linear Programming (ILP) optimal objective values, in order to compute a measure of solution quality: the relative optimality gap. The proposed algorithms are able to efficiently solve instances with sizes beyond what has been so far published in literature, and more importantly, with considerably higher quality, i.e., narrower relative optimality gaps