Back

G-2004-20

ILP Formulations and Optimal Solutions for the RWA Problem

, , , and

BibTeX reference

We present a review of the various integer linear programming (ILP) formulations that have been proposed for the routing and wavelength assignment problem in WDM optical networks with a unified and simplified notation. We consider both symmetrical and asymmetrical traffic matrices. We propose a new formulation for symmetrical traffic. We show that all formulations proposed under asymmetrical traffic assumptions are equivalent (i.e. same optimal value for their continuous relaxations) although their number of variables and constraints differ. We propose an experimental comparison of various lower and upper bounds with the objective of minimizing the blocking rate, and show that several benchmark problems proposed by Krishnaswamy and Sivarajan (2001) can be solved exactly or with a fairly high precision.

, 20 pages