A column generation approach for SONET ring assignment

In this article we consider the SONET ring assignment problem (SRAP). The authors pointed out the inadequacy of solving SRAP instances using their integer programming formulation and commercial linear programming solvers. In this article we reformulate SRAP as a set partitioning model with an additional knapsack constraint. This new formulation has an exponential number of columns and, to solve it, we implemented a branch-and-price/column generation algorithm. Extensive computational experiments showed that the new algorithm is orders of magnitude faster than standard branch-and-bound codes running on compact IP models introduced earlier. Instances taken from earlier papers, which could not be solved there in hours of computation were solved here to optimality in just a few seconds.