An initial polyhedral study of the DR-AOV formulation for the routing and spectrum allocation problem

Abstract

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.