-

 

 

 




Optimization Online





 

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

Arie M.C.A. Koster (koster***at***zib.de)
Adrian Zymolka (zymolka***at***zib.de)

Abstract: 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.

Keywords: Optical Networks, Wavelength Assignment, Integer Programming, Column Generation

Category 1: Applications -- OR and Management Sciences (Telecommunications )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Combinatorial Optimization (Graphs and Matroids )

Citation: ZIB Report 04-41, http://www.zib.de/ An extended abstract will be published in the proceedings of the International Network Optimization Conference, INOC 2005, Lissabon, Portugal.

Download: [Compressed Postscript][PDF]

Entry Submitted: 01/07/2005
Entry Accepted: 01/07/2005
Entry Last Modified: 01/07/2005

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society