^{1} Department of Informatics and Mathematical Modeling, Technical University of Denmark^{2} Operations Research, Department of Informatics and Mathematical Modeling, Technical University of Denmark^{3} Department of Management Engineering, Technical University of Denmark

DOI:

10.1016/j.cor.2005.05.021

Abstract:

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.

Type:

Journal article

Language:

English

Published in:

Computers and Operations Research, 2007, Vol 34, Issue 4, p. 997-1007