A Lagrangean approach to network design problems

Network design is a very important issue in the area of telecommunications and computer networks, where there is a large need for construction of new networks. This is due to technological development (fiber optics for telecommunication) and new ways of usage (Internet for computer networks). Optimal design of such networks requires formulation and solution of new optimization models. In this paper, we formulate several fixed charge network design models, capacitated or uncapacitated, directed or undirected, possibly with staircase costs, and survivability requirements. We propose a common solution approach for all these problems, based on Lagrangean relaxation, subgradient optimization and primal heuristics, which together form a Lagrangean heuristic. The Lagrangean heuristic can be incorporated into a branch-and-bound framework, if the exact optimal solution must be found. The approach has been tested on problems of various structures and sizes, and computational results are presented.