Groupe d’études et de recherche en analyse des décisions

G-2004-95

ILP Formulations for the RWA Problem - Symmetric Systems

, et

Different integer linear programming (ILP) formulations have been proposed for the routing and wavelength assignment problem in WDM optical networks, mainly for asymmetrical systems, more than for symmetrical systems, under different objectives. We propose a synthesis of the mathematical models for symmetrical systems, with a unified and simplified notation for four widely used objectives. As for asymmetrical traffic models (Jaumard, Meyer and Thiongane, 2004), we show that all formulations, both link and path formulations, are equivalent in terms of the bound values provided by the optimal solution of their linear programming relaxation, although their number of variables and constraints differ.

We propose an experimental comparison of the linear relaxation bounds with the optimal ILP solutions whenever it is possible, for several network and traffic instances.

, 44 pages