Telecommunication networks optimization with survivability
Optimisation de réseaux de télécommunications avec sécurisation
Résumé
The first part of this thesis, is concerned with the study of the robustness of the predictor corrector interior point algorithm and with a decomposition approach of this method for solving multicommodity network-flow problems. In the second part, we are concerned with the Global Survivability in Telecommunication Networks (PSG). The objective consists in finding the optimal routing and the least cost investment in base and reserve capacities. The routing and the base capacity insure base traffic and the reserve capacity guarantees survivability of the traffic against any arc failure (using a global rerouting strategy). In our model we consider that routings and capacities can be fractionated. So PSG can be formulated as a large-scale linear program. Its special structure favours the use of decomposition algorithms. We propose four methods using columns generation technics. The first tow are based on proximal decomposition methods. The main task of these algorithm consist in solving independent quadratic subproblems. The third algorithm is inspired by the interior point decomposition approach described in the first part. Finally, we incorporate path elimination procedure into an adaptation of ready-to-use interior points code. We report some numerical results obtained by testing these algorithms with data from the France-Telecom Paris district transmission network.
La première partie de cette thèse, concerne une étude de robustesse des algorithmes de points intérieurs prédicteurs correcteurs, ainsi qu'une approche par décomposition de cette méthode pour la résolution de problè mes de multiflot. Dans la deuxième partie, nous nous intéressons au Problème de Sécurisation Globale dont l'objectif est de déterminer un multiflot (qui transporte toute demande de son noeud origine à son noeud destination en respectant la loi de Kirchhoff) et l'investissement de moindre coût en capacité s nominale et de réserve qui assure le routage nominal et garantit sa survie par reroutage global. Dans notre modèle les routages et les capacités peuvent être fractionnés. PSG se formule alors comme un problème linéaire de grande taille avec plusieurs niveaux de couplage. Sa structure particulière appelle à l'emploi d'algorithmes de décompositions. Nous proposons quatre méthodes utilisant la technique de génération de colonnes. Les deux premières sont basées sur les techniques proximales. Leur tâche principale consiste en la résolution de sous problèmes quadratiques indépendants. Le troisième algorithme s'inspire de l'approche de points intérieurs décrite à la première partie. Pour finir, nous intégrons une procédure d'élimination de chemins dans une adaptation d'un solveur de points intérieurs. Nous reportons des résultats numériques obtenus en testant ces algorithmes sur des données réelles fournies par le CNET.