Title ILP Formulations for the RWA Problem - Asymmetric and Symmetric
Systems

Authors : B. Jaumard, C. Meyer and B. Thiongane

Speaker: B. Jaumard


Different integer linear programming (ILP) formulations have been proposed
for the routing and wavelength assignment problem in WDM optical networks,
mainly for symmetrical and asymmetrical systems, under different objectives.
We propose a synthesis of the mathematical models for both systems, with a
unified and simplified notation for four widely used objectives. We show
that all formulations, for the compact ILP formulations, both link and path
formulations, are equivalent in terms of the upper bound value provided by
the optimal solution of their linear programming relaxation, although their
number of variables and constraints differ. However, those bounds are
improved when considering column generation formulations.

We propose an experimental comparison of the best linear relaxation bounds
bounds with the optimal ILP solutions whenever it is possible, for several
network and traffic instances. Several instances are solved exactly for the
first time.