Tight LP-based lower bounds for wavelength conversion in optical networks

Tight LP-based lower bounds for wavelength conversion in optical networks

0.00 Avg rating0 Votes
Article ID: iaor20072933
Country: Netherlands
Volume: 61
Issue: 1
Start Page Number: 115
End Page Number: 136
Publication Date: Feb 2007
Journal: Statistica Neerlandica
Authors: ,
Keywords: programming: linear
Abstract:

With the introduction of optical switching technology in telecommunication networks, all-optical connections, so-called lightpaths, can be established. Lightpaths have to be assigned a wavelength in such a way that no two lightpaths sharing a fiber use the same wavelength. The wavelength of operation can only be exchanged by the deployment of a wavelength converter. In this paper, we study the minimum converter wavelength assignment problem. We develop three integer programming formulations to minimize the number of converters and study their properties. Where the first two formulations lack the power to provide non-trivial lower bounds, tight lower bounds can be computed by solving the linear relaxation of the third formulation by delayed column generation. In fact, the lower bound equals the best known solution value for all realistic instances at our disposal. In a computational study, we compare different strategies to enhance the column generation algorithm.

Reviews

Required fields are marked *. Your email address will not be published.