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.
A column generation approach for multicast routing and wavelength assignment with delay constraints in heterogeneous WDM networks / F. Colombo, M. Trubian. - In: ANNALS OF OPERATIONS RESEARCH. - ISSN 0254-5330. - 222:1(2014 Nov), pp. 239-260.
|Titolo:||A column generation approach for multicast routing and wavelength assignment with delay constraints in heterogeneous WDM networks|
COLOMBO, FABIO (Primo)
TRUBIAN, MARCO (Ultimo)
|Parole Chiave:||assignment; branch and cut; column generation; combinatorial optimization; OR in telecommunications; tabu search|
|Settore Scientifico Disciplinare:||Settore MAT/09 - Ricerca Operativa|
|Data di pubblicazione:||nov-2014|
|Data ahead of print / Data di stampa:||8-giu-2013|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1007/s10479-013-1403-7|
|Appare nelle tipologie:||01 - Articolo su periodico|