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
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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom