Multi-layer network design problems in telecommunication


Thesis Type: Doctorate

Institution Of The Thesis: Orta Doğu Teknik Üniversitesi, Faculty of Engineering, Department of Industrial Engineering, Turkey

Approval Date: 2013

Student: İNCİ YÜKSEL ERGÜN

Co-Supervisor: ÖMER KIRCA, HALDUN SÜRAL

Abstract:

The telecommunication network design problem is to configure a telecommunication network of major hardware and their links in order to satisfy traffic demands and flows subject to a set of constraints arising from topology, capacity, and technology. Telecommunication network design has been studied in several disciplines and its literature is intricate. In this study, we classify the telecommunication network design problems in the literature from the perspective of operations research and review the network optimization problems to match design problems with optimization problems. Our review examines mainly decision problems, mathematical formulations, and effective solution methods for the relevant network optimization problems. We address the multilayer telecommunication network design problem consisting of networks with several layers working interdependently and investigate its sub-problems and capabilities of existing formulations. We suggest a novel mathematical formulation that models all layers using a single-mega network and incorporates various practical decision problems. Our computational experiments show that the problem instances with more than two layers, which are not computationally tractable with the existing formulations, can be solved using the NFF by general-purpose integer programming solvers. We also develop tailored solution algorithms based on Benders decomposition to solve the large telecommunication network design problems that cannot be handled by general solvers. Consolidating the available test problem instances in the literature, we perform extensive computational experiments on these instances to assess the behavior of the algorithms and to present favorable results.