Premium
Tight LP‐based lower bounds for wavelength conversion in optical networks
Author(s) -
Koster Arie M. C. A.,
Zymolka Adrian
Publication year - 2007
Publication title -
statistica neerlandica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.52
H-Index - 39
eISSN - 1467-9574
pISSN - 0039-0402
DOI - 10.1111/j.1467-9574.2007.00351.x
Subject(s) - column generation , integer programming , wavelength , upper and lower bounds , linear programming , computer science , wavelength division multiplexing , power (physics) , integer (computer science) , column (typography) , relaxation (psychology) , mathematical optimization , topology (electrical circuits) , mathematics , algorithm , telecommunications , physics , optics , combinatorics , psychology , mathematical analysis , social psychology , quantum mechanics , frame (networking) , programming language
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.