Survivable mobile phone network architectures: models and solution methods

We present a mixed-integer programming model for the problem of designing a survivable capacitated network, and describe a cutting plane algorithm for its solution. The model and the solution methods are integrated in our network dimensioning tool, DISCNET. Given a communication demand between each pair of switching nodes in a region, the task is to determine the topology of a telecommunication network connecting the given nodes and to select, from a given set of valid values, a capacity for each potential physical link such that the communication demands are satisfied, even if a network component fails. A solution consists of the chosen links and their capacity, as well as the routings for each demand, in the case of failure-free operation and the case of single component (node or link) failure. We suggest two alternative models to deal with failures of single network components. The first employs diversified paths to guarantee the routing of a specified fraction of each demand without rerouting effort; the second allows rerouting in failure situations. At the end we discuss alternative ways to implement survivability using these two models.