The Ring Spur Assignment Problem: New formulation, valid inequalities and a branch-and-cut approach

A new mathematical model is proposed for the Ring Spur Assignment Problem (RSAP) that arises in the design of next-generation telecommunication networks. In this problem, every node of the network lies either on a ring among a set of bounded disjoint local rings or is spurred by a single arc to another node on a local ring. A special ring, called a tertiary ring, interconnects the local rings. Our new integer programming model employs only O(n2) variables and has a stronger LP relaxation. Several classes of valid inequalities and corresponding separation procedures are presented giving rise to an efficient branch-and-cut solution algorithm. We report optimal solutions for all SNDLib instances including those that have not previously been solved to optimality.