Location problems with covering constraints: models and solution approaches for the telecommunications

Driven by the growing influence of telecommunications in contemporary society, this doctoral thesis offers novel contributions to the modeling and solution of location problems involving covering constraints for the telecommunications. We address two distinct network design problems: the first pertains specifically to the telecommunications sector, while the second has broader applicability to service and communications networks. Specifically, the first contribution focuses on the location of the transmitters, i.e. the facilities enabling wireless connection, to meet service coverage requirements. In the modern context of increasing traffic, establishing suitable locations and power emissions for the transmitters is a relevant but challenging task due to heavy radio spectrum congestion, leading to signal interference and subsequent service degradation. Traditional network design formulations are very ill-conditioned and suffer from numerical inaccuracies and limited applicability to large-scale practical scenarios. Our contribution consists of speeding up the solution of the problem under consideration by addressing its drawbacks from a modeling point of view. We discuss the modeling of the technological constraints concerning the quality of service, and propose valid cutting plans and constraints aggregation, along with various presolve operations to reduce the problem size and strengthen existing formulations. Our proposals prove effective, allowing us to achieve optimality on large-scale scenarios in solution times aligning well with planning windows. The second contribution concerns the introduction of mixed-integer quadratic formulations of a novel problem related to the design of service and communications networks. The problem is a location problem with a covering constraint allowing for partial coverage that takes into consideration both the minimization of the congestion and the protection from the uncertainty in customer demand. In particular, motivated by the contemporary society’s growing demand for high service quality, we penalize congestion responsible for degrading the service and account for uncertainties in a robust framework. To solve this problem, we propose several Benders decomposition approaches and introduce a cut-strengthening technique to efficiently deal with the degeneracy of the Benders subproblem. Our tailored approach clearly outperforms the state-of-the-art solver Gurobi on adapted instances from the literature.