Reducing the Hierarchical Network Design Problem

The Hierarchical Network Design Problem (HNDP) can be seen as a minimum spanning tree problem involving two weight functions. It is shown that the HNDP is a special case of the Directed Steiner Tree Problem. Theorems are given to obtain optimal arcs, that are used in a Lagrangean relaxation of the linear programming model. Reduction tests, reducing the size of the problem graph and/or eliminating variables from this program, are specialized and developed for the HNDP. The presented techniques are illustrated on example problems from the literature and computational results for the reduction tests are given.