Formulations and algorithms to design communication networks

Abstract

The study of networks has roots in graph theory dating back to 1730s. From then on, networks have been used to model and simulate interactions among elements of intricate systems, such as transportation, communication and computer ones. Communication networks are widely used to exchange information among entities of a system. The importance of communication networks has dramatically increased over the past few years, drawing attention to the design stage of a real system, giving rise to many optimization problems. Operations Research techniques and solutions have been playing a fundamental role across a wide range of network design problems. In this thesis, we study how to apply optimization techniques in the design of communication networks. Firstly, we dedicate to the problem of designing hierarchical telecommunication networks ensuring resilience against random failures and maximum delay guarantees in the communication. After, we study how to design efficient communication networks based on complex networks features. A set of metrics is used as optimization criteria while designing such networks. Finally, we investigate solutions to the routing and wavelength assignment problem with traffic grooming, protection and quality of service on WDM optical networks. Different mathematical formulations to model the three problems are proposed. A Branch-and-bound algorithm based on compact formulations is evaluated and compared to a Branch-and-price approach based on extended formulations of the problems. Our comparative analysis demonstrates that the proposed Branch-and-price approach is able to solve problems whose dimensions are out of reach for other traditional optimization tools.