Nested Column Generation Algorithm for the Routing and Spectrum Assignment Problem in Flexgrid Optical Networks

With the ever increasing demand for optical networks, many decisions about network planning are becoming increasingly challenging. One of these crucial decisions is the network provisioning, known as the Routing and Spectrum Assignment (RSA) problem. What makes this problem practically challenging to service providers is the significant difference in size between the realistic problem instances and the instances that can be solved using the existing algorithms. Motivated to solve larger problem sizes, we propose a decomposition model and a nested column generation algorithm for the RSA problem. Compared to recent studies, the proposed algorithm produces higher-quality solutions for larger data instances quite efficiently. Furthermore, it provides a measure of the solution accuracy, i.e., an upper bound on the maximum distance of the solution obtained compared to the optimal solution.