The ring spur assignment problem: new formulation, valid inequalities and a branch-and-cut approach

Rahimeh Neamatian Monemi, Shahin Gelareh

Research output: Contribution to journalArticlepeer-review

64 Downloads (Pure)

Abstract

A new mathematical model is proposed for the Ring Spur Assignment Problem (RSAP) that arises in the design of next-generation telecommunication networks. In this problem, every node of the network lies either on a ring among a set of bounded disjoint local rings or is spurred by a single arc to another node on a
local ring. A special ring, called a tertiary ring, interconnects the local rings. Our new integer programming model employs only O(n2) variables and has a stronger LP relaxation. Several classes of valid inequalities and corresponding separation procedures are presented giving rise to an efficient branch-and-cut solution algorithm. We report optimal solutions for all SNDLib instances including those that have not previously been solved to optimality.
Original languageEnglish
Pages (from-to)91-102
JournalComputers & Operations Research
Volume88
Early online date22 Jun 2017
DOIs
Publication statusPublished - Dec 2017

Keywords

  • location-allocation
  • branch-and-cut
  • next-generation telecommunications networks

Fingerprint

Dive into the research topics of 'The ring spur assignment problem: new formulation, valid inequalities and a branch-and-cut approach'. Together they form a unique fingerprint.

Cite this