Integer programming formulations for the survivable routing and spectrum assignment problem with path protection

Abstract

The routing and spectrum assignment (RSA) problem arises in the context of planning fiber optical networks, and consists in establishing lightpaths for a set of demands given by an origin node, a destination node, and a number of frequencly slots. Each lightpath is determined by a route and a channel, and RSA consists in finding these elements for each demanda. The survivable RSA with path protection is a variante of RSA, which asks two lightpaths for each demand, namely an original path and a backup path, both obeying the RSA constraints. This problem is NP-hard.

In this work we propose several integer programming formulations for this problem, and we study their performance over real instances. We present several families of valid inequalities for one of these formulations, and we study their impact on the practical resolution of this model.