责任导师 : Michel MINOUX

助理责任导师 : GABREL Virginie

Modèles et algorithmes de multiflots à coût discontinu pour l'optimisation réseaux de télécommunications

Cette thèse porte sur l'optimisation de réseaux de télécommunications : comment répartir les capacités sur les liens d'un réseau de façon à minimiser le coût global tout en satisfaisant un ensemble de demandes de trafic ? Les coûts sur les liens du réseau sont modélisés ici par des fonctions de coût croissantes en escalier quelconques et le problème est mis sous la forme d'un programme linéaire en nombres entiers. Deux approches distinctes ont donné lieu à des algorithmes originaux de résolution exacte ou approchée pour les problèmes de flot simple puis de multiflot, qui compte tenu des fonctions de coût sont d'une très grande complexité combinatoire.
Le cas du flot simple est traité au moyen d'un algorithme exact d'énumération implicite et par une méthode de génération de contraintes. L'algorithme d'énumération implicite a permis la mise au point d'une méthode de résolution approchée pour le cas du multiflot qui améliore des résultats antérieurs. La méthode de génération de contraintes a pu être adaptée au cas du multiflot et a permis d'obtenir des solutions exactes pour des problèmes de réseaux ayant une vingtaine de sommets et une quarantaine d'arêtes. Cette approche a également été généralisée pour la résolution exacte du problème de dimensionnement de réseaux résistants aux pannes, où l'on veut que toutes les demandes de trafic puissent être satisfaites même en cas de panne sur un lien quelconque du réseau. Enfin, des solutions approchées de bonne qualité sont obtenues par génération de contraintes au moyen d'une résolution approchée des sous-problèmes.
Tous ces algorithmes sont présentés avec des résultats d'expériences numériques réalisées à partir de problèmes générés aléatoirement.

1998-2007 刊物

• 2007
  • V. Nguyen, A. Knippel : “On Tree Star Network design”, International Network Optimization Conference, Spa, Belgium, pp. 1-6 (2007)
• 2004
  • A. Knippel : “Accelerating a Bender’s Method for Network Design”, International Conference in Modelling, Computation and Optimization in Information Systems and Management Sciences,, Metz, France, pp. 209-214 (2004)
  • B. Lardeux, J. Geffard, A. Knippel : “Algorithmes pour le problème d’expansion de réseau sur deux couches”, ALGOTEL 2004 - 6^es Rencontres Francophones sur les aspects Algorithmiques des Télécommunications, Batz-sur-mer, France (2004)
• 2003
  • V. Gabrel, A. Knippel, M. Minoux : “A comparison of heuristic for the discrete cost multicommodity network optimization problem”, Journal of Heuristics, vol. 9 (5), pp. 429-445, (Springer Verlag) (2003)
  • B. Lardeux, A. Knippel, J. Geffard : “Efficient algorithms for solving the 2-layered network design problem.”, International Network Optimization Conference, Evry/Paris, France, pp. 367-372 (2003)
  • A. Knippel : “Polyèdres de multiflots et génération de constraintes”, Journées Polyèdre et Optimisation Combinatoire, Clermont-Ferrand, France (2003)
  • B. Lardeux, A. Knippel, J. Geffard : “Dimensionnement de réseaux de télécommunication sur deux couches”, 5^e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2003), Avignon, France (2003)
  • V. Gabrel, A. Knippel, M. Minoux : “Etude comparative d’heuristiques pour la résolution du problème de dimensionnement de réseaux de télécomunications avec coûts discrets”, 5^e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2003), Avignon, France (2003)
• 2002
  • A. Knippel, V. Gabrel, M. Minoux : “Solving exactly the Discrete Cost Flow Problem”, International Symposium on Combinatorial Optimization, Paris, France (2002)
• 2001
  • A. Knippel : “Modèles et algorithmes de multiflots à coût discontinu pour l’optimisation réseaux de télécommunications”, 博士论文, 答辩 2001-6-26, 责任导师 Minoux, Michel, 助理责任导师 : Gabrel, Virginie (2001)
  • A. Knippel, V. Gabrel, M. Minoux : “Approximate solutions for hard network design problems”, EURO2001, Rotterdam, Netherlands (2001)
  • A. Knippel, T. Q. Nguyen : “Approche glouton et algoritme D.C. appliquée au problème de dimensionnement de réseaux de télécommunication”, FRANCORO III, Quebec, Canada (2001)
• 2000
  • A. Knippel, V. Gabrel, M. Minoux : “Résolution exacte de problèmes d’optimisation de réseaux résistant aux pannes”, AlgoTel 2000 - 2^es Rencontres Françaises sur les Aspects Algorithmiques des Télécommunications, La Rochelle, France (2000)
  • V. Gabrel, A. Knippel, M. Minoux : “Solution exacte aux problèmes de multiflots avec fonctions de coût en escalier”, 3^e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2000), Nantes, France (2000)
• 1999
  • V. Gabrel, A. Knippel, M. Minoux : “Exact Solution of Multicommodity Network Optimization Problems with General Step Cost Functions”, Operations Research Letters, vol. 25 (1), pp. 15-23, (Elsevier) (1999)
  • A. Knippel, T. Q. Nguyen : “Méthodes approchées pour le problème de dimensionnement des réseaux de télécommunications”, ALGOTEL 99, Roscoff, France (1999)
  • V. Gabrel, A. Knippel, M. Minoux : “Heuristiques pour le problème du multiflot à coût minimum avec fonctions de coût en escalier”, 2^e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 1999), Autrans, France (1999)
• 1998
  • A. Knippel, V. Gabrel, M. Minoux : “Network Optimisation with Step-Increasing Cost Functions: Approximate Algorithms and LP-Based Lower Bounds”, Computational Engineering in Systems Applications - IMACS Multiconference, Nabeul-Hammamet, Tunisia (1998)
  • A. Knippel : “Approches heuristiques du problème de multiflot de coût minimum et fonctions de coût en escalier”, 1^er Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 1998), Paris, France (1998)