Improved ILP Models and Heuristics for Solving Routing and Resource Allocation Problems in Optical Networks

Integer linear programming (ILP) is an exact method for solving optimization problems; however, its application to large-scale scenarios often becomes impractical due to its exponentially increasing time complexity. To overcome this limitation, heuristic algorithms have been developed to efficiently identify near-optimal solutions. Both methods are widely used for routing and resource allocation in optical networks. Elastic Optical Networks (EONs) improve network capacity and spectral efficiency through granular spectrum division using frequency slots (FS), enabling dynamic spectrum allocation. Nevertheless, this flexibility introduces additional complexity to the Routing and Spectrum Assignment (RSA) problem. In this paper, we present improved ILP models for Routing and Wavelength Assignment (RWA) and RSA problems, highlighting how the properties of the model's coefficient matrix, such as total unimodularity and symmetry, influence performance Additionally, we propose a novel Two-Stage Graph Coloring-based Row Generation (TSGCRG) heuristic algorithm tailored for large-scale RWA and RSA issues. Our experiments conducted across networks and service request matrices of varying scales demonstrate that our proposed ILP models and heuristic algorithms yield superior solutions with reduced computation time compared to existing works. Furthermore, we discuss the impact of the number of candidate paths on the ILP path model and find that using 3 or 5 candidate paths is generally the most recommended choice. This integration of exact and heuristic methods offers practical and optimized solutions for managing optical networks across different problem scales.