A Branch and Cut Algorithm for the Ring Spur Assignment Problem

The Ring Spur Assignment Problem (RSAP) arises in the design of Next Generation Telecommunications Networks (NGNs) and has applications in location-allocation problems. The aim is to identify a minimum cost set of interconnected ring spurs. We seek to connect all nodes of the network either on a set of bounded disjoint local rings or by a single spur edge connected to a node on a local ring. Local rings are interconnected by a special ring called the tertiary ring. We show that the problem is NP-Hard and present an Integer Programming formulation with additional valid inequalities. We implement a branch-and-cut algorithm and present our conclusions with computational results.