Optimization of Contemporary Telecommunications Networks: Generalized Spanning Trees and WDM Optical Networks

Abstract

We present a study of two NP-hard telecommunications network design problems - the prize-collecting generalized minimum spanning tree problem (PCGMST) and the design of optical networks with wavelength division multiplexing. The first problem, the PCGMST problem, involves the design of regional backbone networks, where a set of local area networks (LANs) need to be connected by a minimum cost tree network using exactly one gateway site from each LAN. We present several polynomial time heuristics for the PCGMST problem and show that these algorithms, at best, provide only modest quality solutions. We also present two metaheuristics - a local search procedure and a genetic algorithm, and show that these procedures provide compelling high-quality results on a large set of test problems. Our study of the PCGMST problem is concluded by a presentation of two exact solution procedures that can be used to find optimal solutions in networks of moderate size. The second problem studied in this dissertation is a more complex network design problem that involves optical networks with wavelength division multiplexing (WDM). These networks provide an abundance of transmission bandwidth, but require the use of expensive equipment, which, in turn, mandates careful use of the resources available for their design. The novel aspect of WDM optical networks is that they require simultaneous design of two network layers. The first layer is the virtual topology that requires routing of logical paths over the physical layer of optical fibers. The second layer involves routing and grooming of traffic requests over the logical paths established in the virtual topology. This problem has been extensively studied in the last 10 years, but due to its notoriously hard nature, only few exact solution procedures for relaxed versions of this problem were developed so far. We propose one exact and two approximate branch-and-price algorithms for two versions of the WDM optical network design problem and present results of the computational study involving two different design objectives. Finally, we propose two classes of valid inequalities for our branch-and-price algorithms, and discuss applicability of our algorithms to different versions of the WDM optical network design problem.