The generalized fixed-charge network design problem

The generalized fixed-charge network design problem

0.00 Avg rating0 Votes
Article ID: iaor20081559
Country: United Kingdom
Volume: 34
Issue: 4
Start Page Number: 997
End Page Number: 1007
Publication Date: Apr 2007
Journal: Computers and Operations Research
Authors: ,
Keywords: networks, programming: integer
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.

Reviews

Required fields are marked *. Your email address will not be published.