Linear Programming Lower Bounds for Minimum Converter Wavelength Assignment in Optical Networks

Please always quote using this URN: urn:nbn:de:0297-zib-8160

In this paper, we study the conflict-free assignment of wavelengths to lightpaths in an optical network with the opportunity to place wavelength converters. To benchmark heuristics for the problem, we develop integer programming formulations and study their properties. Moreover, we study the computational performance of the column generation algorithm for solving the linear relaxation of the most promising formulation. In many cases, a non-zero lower bound on the number of required converters is generated this way. For several instances, we in fact prove optimality since the lower bound equals the best known solution value.

Metadaten
Author:	Arie M.C.A. Koster, Adrian Zymolka
Document Type:	ZIB-Report
Tag:	integer programming; optical networks; wavelength assignment
MSC-Classification:	90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B18 Communication networks [See also 68M10, 94A05]
	90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C10 Integer programming
	90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C90 Applications of mathematical programming
Date of first Publication:	2004/10/26
Series (Serial Number):	ZIB-Report (04-41)
ZIB-Reportnumber:	04-41
Published in:	A revised version appeared under the title "Tight LP-based Lower Bounds for Wavelength Conversion in Optical Networks" in: Statistica Neerlandica 61:1 (2007) 115-136. Appeared in: Proceeding of INOC 2005, International Network Optimization Conference, March 20-23, 2005 Lissabon, Portugal, pp 44-51

Open Access