Fast Exact ILP Decompositions for Ring RWA
Wavelength division multiplexing rings are now capable of supporting more than 100 wavelengths over a single fiber. Conventional link and path formulations for the routing and wavelength assignment problem are inefficient due to the inherent symmetry in wavelength assignment and the fact that the problem size increases fast with the number of wavelengths. Although a formulation based on Maximal Independent Sets (MIS) does not have these drawbacks, it suffers from exponential growth in the number of variables with increasing network size. The authors develop a new ILP (Integer Linear Program) formulation based on the key idea of partitioning the path set and representing the MIS in the original network using the independent sets calculated in each of these partitions.