A column generation approach for multicast routing and wavelength assignment with delay constraints in heterogeneous WDM networks
Articolo
Data di Pubblicazione:
2014
Citazione:
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.
Abstract:
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.
Tipologia IRIS:
01 - Articolo su periodico
Keywords:
assignment; branch and cut; column generation; combinatorial optimization; OR in telecommunications; tabu search
Elenco autori:
F. Colombo, M. Trubian
Link alla scheda completa: