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

    88 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