A Dual Ascent Procedure with Valid Inequalities for Designing Hierarchical Network Topologies

INFORMS Journal on Computing · 1998 · Volume 10 · Issue 1

Abstract

Topological design of communication networks has been well examined in the literature. However, most of these studies focus on nonhierarchical networks where all nodes are considered equivalent from a routing perspective. It is well recognized, however, that hierarchical topologies offer several advantages for remote office internetworking. In this article, we provide a mixed integer programming formulation for designing hierarchical topologies. We also provide an interesting solution strategy that incorporates valid inequalities within a dual ascent framework to obtain tight lower bounds and feasible solutions to the problem. Computational experiments with a Fortran implementation of the procedure are also reported.

Keywords

Networks, graphs, communications

Enable JavaScript for citation tools and additional paper interactions.