Applications of Combinatorial Optimization, 2nd Edition

Chapter 7

A Model for the Design of a Minimum-cost Telecommunications Network

7.1. Introduction

This chapter is the fruit of a collaboration between the LAMSADE laboratory and Bouygues Télécom with the goal of solving problems linked to interconnecting their mobile telephone network and the France Télécom network. The project was initiated by Bouygues Télécom’s Research and Development department to meet the specific needs identified by its operations entities.

Two problems arise in the design of telecommunications networks: firstly, what network should be constructed to satisfy a given traffic demand (least-cost feasible network design problem); then, how should the various traffics be routed in the existing network (routing or minimum cost multiflow problem). These two questions, independent of course, correspond to two types of financial concerns: the costs of constructing the lines on the one hand, whose form we cannot predict, and the costs of traffic flow over a line on the other hand, generally considered as (possibly piecewise) linear functions of the traffic. These two problems are known for their resolution difficulty: in their general formulation, they have been shown to be NP-hard. The complexity of these two subproblems and their place at the heart of the global problem leads us to imagine the difficulty of the latter. Note that, furthermore, constructing networks lays down requirements in terms of robustness and security, aspects that are not taken into consideration ...