Abstract

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.