Enhanced RWA Exact Solution with a New Lightpath Decomposition Algorithm

The Routing and Wavelength Assignment (RWA) problem has been extensively studied, using both heuristic and exact algorithms. It is now possible to solve exactly large practical RWA instances, i.e., networks with up to 100 nodes and 100 wavelengths in reasonable computational times. In this study, we revisit the lightpath decomposition mathematical model and show that it can lead to a simple and extremely efficient decomposition algorithm. Computational results show that very large RWA instances can be solved exactly within a few minutes (up to 42 times faster than the previous best algorithm, and 5 times faster on average), with an improved proven accuracy (less than 1% for nearly all data sets). In addition, we provide an analysis of the characteristics of the optimal RWA provisioning, in terms of the percentage of the number of routes corresponding to shortest paths. Indeed, their number may decrease to about 50% in some data instances, due to a possible short-sighted network dimensioning.