Abstract

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.