Paper Info
Title
A column generation approach for Multicast Routing and Wavelength Assignment with Delay Constraints in heterogeneous WDM networks.
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.
Year
DOI
Venue
2014
10.1007/s10479-013-1403-7
Annals OR
Keywords
Field
DocType
Combinatorial optimization,Column generation,Branch and cut,Tabu search,Assignment,OR in telecommunications
Heuristic,Mathematical optimization,Column generation,Branch and cut,Routing and wavelength assignment,Combinatorial optimization,Integer programming,Multicast,Linear programming relaxation,Mathematics
Journal
Volume
Issue
ISSN
222
1
0254-5330
Citations 
PageRank 
References 
0
0.34
17
Authors
2
Name
Order
Citations
PageRank
Fabio Colombo141.48
Marco Trubian259451.20