The routing and spectrum allocation (RSA) problem is a critical challenge in optical networks, in which the objective is to assign a path and a set of contiguous frequency slots to each demand, meeting technical constraints given by the network infrastructure. As a key solution to managing large-scale data traffic in such networks, RSA has gained significant attention in the last years. One of the most effective integer programming formulations for RSA is the so-called DR-AOV model, and it is relevant to gain both theoretical and practical insights on this formulation. In this work, we tackle the first of these by starting a polyhedral study of the convex hull of the feasible solutions of the DR-AOV model. We identify general properties of this polytope, we establish relations to interval coloring polytopes, and we present several families of facet-inducing inequalities.

The routing and spectrum allocation (RSA) problem arises in the context of flexible grid optical networks, and consists in routing a set of demands through a network while simultaneously assigning a bandwidth to each demand, subject to non-overlapping constraints. One of the most effective integer programming formulations for RSA is the DR-AOV formulation, presented in a previous work. In this work we explore a relaxation of this formulation with a subset of variables from the original formulation, in order to identify valid inequalities that could be useful within a cutting-plane environment for tackling RSA. We present basic properties of this relaxed formulation, we identify several families of facet-inducing inequalities, and we show that they can be separated in polynomial time.