A Branch and Cut Algorithm for the Ring Spur Assignment Problem

Files in This Item:
File Description SizeFormat 
Carroll_RingSpurBranchCut_Submitted_Networks.pdf558.13 kBAdobe PDFDownload
Title: A Branch and Cut Algorithm for the Ring Spur Assignment Problem
Authors: Carroll, Paula
Fortz, Bernard
Labbé, Martine
McGarraghy, Sean
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 DesignNP-Hardness ProofIP FormulationBranch-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

Citations 50

Last Week
Last month
checked on Oct 20, 2018

Google ScholarTM



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.