New formulations and solution procedures for the hop constrained network design problem

Optical fiber provides tremendous advantages in being able to carry a wide range of services including video on demand, video conferencing, distance learning, remote medical imaging, and telecommuting. The high capacities encourage carriers to create networks that are substantially sparser than previous copper based networks. A recent publication by the Telecommunications Industry Association indicated that investment in fiber optics is projected to reach $35 billion in the year 2003. Given the magnitude of investments, the design of networks becomes a very important issue. Most telecommunication companies (telcos), IT consulting companies, network equipment manufacturers and network service providers have extensive network design groups. The primary function of these groups is to design the most efficient networks both in terms of costs and performance and maintain them. These designers need flexible tools to support topological network design decisions. These decisions involve significant levels of investments in transmission and switching facilities, and impact the resulting networks' performance fundamentally. In this paper we study a special type of a network design problem called the hop constrained backbone network design problem. We present new mathematical programming formulations of the problem and develop an efficient solution procedure based on the linear programming relaxation. Extensive computational results across a number of networks are reported.