A DUAL-BASED ALGORITHM FOR MULTILEVEL NETWORK DESIGN

Given an undirected network with L possible facility types for each ed ge, and a partition of the nodes into L levels or grades, the Multi-le vel Network Design (MLND) problem seeks a fixed cost minimizing design that spans all the nodes and connects the nodes at each level by faci lities of the corresponding or higher grade. This problem generalizes the well-known Steiner network problem and the hierarchical network de sign problem, and has applications in telecommunication, transportatio n, and electric power distribution network design. In a companion pape r we studied alternative model formulations for a two-level version of this problem, and analyzed the worst-case performance of several heur istics based on Steiner network and spanning tree solutions. This pape r develops a dual-based algorithm for the MLND problem. The method fir st performs problem preprocessing to fix certain design variables, and then applies a dual ascent procedure to generate upper and lower boun ds on the optimal value. We report extensive computational results on large, random two-level test problems (containing up to 500 nodes, and 5,000 edges) with varying cost structures. The integer programming fo rmulation of the largest of these problems has 20,000 integer variable s and over 5 million constraints. Our tests indicate that the dual-bas ed algorithm is very effective, producing solutions that are within 0. 9% of optimality.