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 ...
Get Applications of Combinatorial Optimization, 2nd Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.