A matheuristic for the routing and spectrum allocation problem

One of the most promising solutions to deal with huge data traffic demands in large communication networks is given by flexible optical networking, in particular the flexible grid (flexgrid) technology specified in the ITU-T standard G.694.1. In this specification, the frequency spectrum of an optical fiber link is divided into narrow frequency slots. Any sequence of consecutive slots can be used as a simple channel, and such a channel can be switched in the network nodes to create a lightpath. In this kind of networks, the problem of establishing lightpaths for a set of end-to-end demands that compete for spectrum resources is called the routing and spectrum allocation problem (RSA). Due to its relevance, this NP-hard problem has been intensively studied in the last decade. In this work we present an integer-programming-based heuristic for RSA. We propose several measures of the instance density, and we explore the performance of the proposed heuristic procedure as a function of these measures. Our computational experience shows that the proposed heuristic is effective for tackling RSA, in particular for detecting probably infeasible instances. We report the impact of the addition of this heuristic to an existing branch-and-cut procedure, showing that this addition enhances the ability of this procedure to solve realistic instances with optimality. Finally, we propose an instance benchmark in order to allow the comparison among different methods for RSA, a feature that was lacking in the RSA literature up to this point.