OPTIMAL-DESIGN OF A DISTRIBUTED NETWORK WITH A 2-LEVEL HIERARCHICAL STRUCTURE

This paper deals with the topological design of a network with a two-level hierarchical structure where the embedded backbone network is full-meshed and the local networks attached to it are of star type. The whole problem, unlike the conventional approaches partitioning it into two subproblems, is directly handled in such a general setting that both a backbone network and local access networks are to be simultaneously determined. We formulate this problem as a quadratic 0-1 programming model, and also propose an equivalent linearized version of the model. Based on the observation that the linearized model is a variant of the well established uncapacitated facility location problem, a dual-based solution procedure is developed and shown to be efficient from computing experiments which were done on a wide variety of problems with up to 50 backbone nodes and 50 user nodes.