Routing and wavelength assignment in survivable wavelength-division multiplexing networks without wavelength conversion

In this paper, we consider the routing and wavelength assignment problem in survivable WDM transport network without wavelength conversion. We assume the single-link failure and a path protection scheme in optical layer. When a physical network and a set of working paths are given, the problem is to select a link-disjoint protection path for each working path and assign a wavelength for each working and protection path. We give an integer programming formulation of the problem and propose an algorithm to solve it. Though the formulation has exponentially many variables, we solve the linear programming relaxation of it by using column generation technique. We devise a branch-and-price algorithm to solve the column generation problem. After solving the linear programming relaxation, we apply a variable fixing procedure combined with the column generation to get an integral solution. We test the proposed algorithm on some randomly generated data and test results show that the algorithm gives very good solutions.