An Efficient Column Generation Approach for Solving the Routing and Spectrum Assignment Problem in Elastic Optical Networks

Routing and spectrum assignment (RSA) is an essential problem in designing, operating and managing elastic optical networks to achieve spectrum efficiency and thus, efficient algorithms for solving the RSA has been of crucial importance. The conventional Mixed Integer Linear Programming (MILP) formulation has a critical drawback of scalability and hence has been applicable to only small data instances while heuristic-based approach is prone to locally optimal solutions without guarantees for global optimality. In order to mitigate the scalability issue of the traditional MILP models and possibly low-quality solutions from heuristic, we investigate an approach based on the column generation (CG) method for solving the RSA problem by presenting an efficient CG-based formulation and numerically evaluate it on various realistic network topologies with full mesh traffic. The performance of our CG-based approach is benchmarked with the typical heuristic, First-Fit algorithm, and it has been revealed that our CG proposal can provide better solutions in most cases and the solution gap could be up to more than 20%.