The Generalized Fixed-Charge Network Design Problem

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.