A heuristic for the topological design of two-tiered networks

A basic hierarchical network design problem is that of selecting access area and backbone designs that minimize the sum total cost of the network. Because of its computational difficulty, network designers typically segment the hierarchical design problem, first solving the access area problem to obtain a set of backbone nodes and then solving the backbone design problem on the subgraph induced by these nodes. Each individual problem is far easier to solve than the complete network design problem, but in general the procedure gives a poor overall solution. In this paper, we describe a technique for integrating the access area and backbone design problems into a single mathematical program. The fundamental idea of this approach is to incorporate backbone network cost information into the access area problem without increasing the computational difficulty of the resulting problem significantly beyond that of the access area problem