Premium
A branch‐and‐cut algorithm for the ring spur assignment problem
Author(s) -
Carroll Paula,
Fortz Bernard,
Labbé Martine,
McGarraghy Seán
Publication year - 2013
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21495
Subject(s) - ring (chemistry) , integer programming , computer science , bounded function , node (physics) , algorithm , branch and cut , set (abstract data type) , spur , enhanced data rates for gsm evolution , disjoint sets , integer (computer science) , mathematics , discrete mathematics , telecommunications , engineering , mathematical analysis , chemistry , organic chemistry , structural engineering , programming language
Abstract The ring spur assignment problem arises in the design of next‐generation telecommunications networks 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 N P ‐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. © 2013 Wiley Periodicals, Inc. NETWORKS, 2013