A Branch and Cut Algorithm for the Ring Spur Assignment Problem
Files in This Item:
|Carroll_RingSpurBranchCut_Submitted_Networks.pdf||558.13 kB||Adobe PDF||Download|
|Title:||A Branch and Cut Algorithm for the Ring Spur Assignment Problem||Authors:||Carroll, Paula
|Permanent link:||http://hdl.handle.net/10197/9428||Date:||Mar-2013||Abstract:||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.||Type of material:||Journal Article||Publisher:||Wiley||Journal:||Networks||Volume:||61||Issue:||2||Start page:||89||End page:||103||Copyright (published version):||2013 Wiley||Keywords:||Survivable Network Design; NP-Hardness Proof; IP Formulation; Branch-and-Cut Algorithm||DOI:||10.1002/net.21495||Language:||en||Status of Item:||Peer reviewed|
|Appears in Collections:||Business Research Collection|
Show full item record
This item is available under the Attribution-NonCommercial-NoDerivs 3.0 Ireland. No item may be reproduced for commercial purposes. For other possible restrictions on use please refer to the publisher's URL where this is made available, or to notes contained in the item itself. Other terms may apply.