The Generalized Fixed-Charge Network Design Problem

Tommy Thomadsen, Thomas K. Stidsen

    Research output: Contribution to journalJournal articleResearchpeer-review


    In this paper we present the generalized fixed-charge network design (GFCND) problem. The GFCND problem is an instance of the so-called generalized network design problems. In such problems, clusters instead of nodes have to be interconnected by a network. The network interconnecting the clusters is a fixed-charge network, and thus the GFCND problem generalizes the fixed-charge network design problem. The GFCND problem is related to the more general problem of designing hierarchical telecommunication networks. A mixed integer programming model is described and a branch-cut-and-price algorithm is implemented. Violated constraints and variables with negative reduced costs are found using enumeration. The algorithm is capable of obtaining optimal solutions for problems with up to 30 clusters and up to 300 nodes. This is possible, since the linear programming relaxation bound is very tight and there are few non-zero variables and few binding constraints.
    Original languageEnglish
    JournalComputers and Operations Research
    Issue number4
    Pages (from-to)997-1007
    Publication statusPublished - 2007


    Dive into the research topics of 'The Generalized Fixed-Charge Network Design Problem'. Together they form a unique fingerprint.

    Cite this