A column generation approach for multicast routing and wavelength assignment with delay constraints in heterogeneous WDM networks

Wavelength Division Multiplexing (WDM) optical networks are increasingly used to build up backbone networks. In this paper we study the Multicast Routing Wavelength Assignment with Delay Constraints (MRWA-DC) problem: given a WDM network with heterogeneous splitting capabilities, we want to find an optimal light-forest that respects delay bound constraints. We propose a new Integer Linear Programming compact formulation and we derive from it a new extended formulation. We solve the Linear Programming relaxation of the latter formulation using a column generation algorithm, and to address the resulting pricing problem we propose two exact algorithms and a tabu search heuristic. Experimental results show that in most cases the solutions obtained from the Linear Programming relaxation of the extended formulation are integral and that the combination of exact and heuristic algorithms for the pricing problem allows to reduce the total computation time required by the column generation process. With respect to the previous literature on the same problem we significantly reduce the computation time required for solving instances of comparable dimension and we solve, within a reasonable computation time, new instances of larger size.