A Hub Location Problem with Fully Interconnected Backbone and Access Networks

Tommy Thomadsen, Jesper Larsen

    Research output: Contribution to journalJournal articlepeer-review

    Abstract

    This paper considers the design of two-layered fully interconnected networks. A two-layered network consists of clusters of nodes, each defining an access network and a backbone network. We consider the integrated problem of determining the access networks and the backbone network simultaneously. A mathematical formulation is presented, but as the linear programming relaxation of the mathematical formulation is weak, a formulation based on the set partitioning model and column generation approach is also developed. The column generation subproblems are solved by solving a series of quadratic knapsack problems. We obtain superior bounds using the column generation approach than with the linear programming relaxation. The column generation method is therefore developed into an exact approach using the Branch-and-Price framework. With this approach we are able to solve problems consisting of up to 25 nodes in reasonable time. Given the difficulty of the problem, the results are encouraging.
    Original languageEnglish
    JournalComputers & Operations Research
    Volume34
    Issue number8
    Pages (from-to)2520-2531
    ISSN0305-0548
    DOIs
    Publication statusPublished - 2007

    Bibliographical note

    Accepted for publication

    Keywords

    • Hub location
    • Branch-and-Price
    • Fully interconnected networks
    • Hierarchical networks

    Fingerprint

    Dive into the research topics of 'A Hub Location Problem with Fully Interconnected Backbone and Access Networks'. Together they form a unique fingerprint.

    Cite this