A branch‐and‐cut algorithm for the ring spur assignment problem. Issue 2 (28th January 2013)

• Record Type: Journal Article
• Authors: Fortz, B.; Carroll, Paula; Fortz, Bernard; Labbé, Martine; McGarraghy, Seán; Gouveia, Luis; Voß, Stefan
• Is Part Of: Networks. Volume 61:Issue 2(2013:Mar.)
• Page Start: 89
• Page End: 103
• Publication Date: 2013-01-28
• Subjects: Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21495
• Languages: English
• ISSNs: 0028-3045

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>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 <italic>N</italic><italic>P</italic> ‐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</p> </abstract>