Optimisation of the interconnecting network of a UMTS radio mobile telephone system

In this paper we address a very important optimisation problem arising in the telecommunications field, namely the design of the interconnecting network of a UMTS radio mobile telephone system. For this NP-hard optimisation problem we propose a new mixed-integer linear programming model, as well as several classes of additional constraints meant at improving the performance of solution algorithms and the quality of the lower bounds produced. Afterwards, we introduce an exact solution procedure in the branch-and-cut framework, and evaluate it on a library of real-life test problems provided by CSELT, a major research laboratory operating with an Italian telephone operator (TELECOM Italia). We report on our computational experience on these test instances, showing that the method we propose is capable of finding tight lower bounds and approximate solutions for real-world instances, within acceptable computing time.