Decomposition Methods for the Optimization of Survivable Telecommunications Networks

Nowadays, survivability in telecommunication networks is a crucial problem in networks optimization. Given a set of requirements, which correspond to single or multicommodity flows, the survivable network design problem (SNDP ) consists in determining a minimum cost network topology and capacity assignment such that all traffic demands are satisfied, especially in the case of link or node failure. In the literature, it is generally proposed that a reserve network is added to the main one in order to provide an additional capacity used only in the case of failure. Because capacity in telecommunications is a key resource, keeping excess capacity is expensive for telecommunication companies, but the inability to transfer data, even for a limited time, could be seen as unacceptable to the user, and consequently have an indirect impact on the profitability of the company. In this research, we are primarily interested in proposing a Linear Programming model, taking into account, on the one hand, specificity of failure occurrences, and on the other hand, an optimal traffic re-allocation or rerouting (global vs local) strategies. We also investigate the relevance and the performance of applying decomposition techniques (like the Benders Decomposition) to this kind of problems.