Topological design of a two-level network with ring-star configuration

This paper deals with topological design of a hierarchical two-level network where the upper-level hub network is of ring type and the lower-level local access networks are of star-type. The problem is modeled as a mixed 0-1 integer programming, the special structure of which is exploited for the development of a dual-based lower bounding procedure. A heuristic procedure is developed to construct a primal feasible solution from the dual solution obtained by the dual procedure. The performance of the present method is well demonstrated by the computational experiments conducted with a variety of test problems ranging up to 20 hub nodes and 50 user nodes.