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

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.