KNIPPEL Arnaud
Gruppo di ricerca : DECISION
Data di partenza : 08/31/2004
https://lip6.fr/Arnaud.Knippel
Relatore : Michel MINOUX
Co-relazione : 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.
Difesa : 06/26/2001
Membri della commissione :
Monoux Michel, Professeur UPMC, directeur
Gabrel Virginie, MCF, paris XIII, co-directrice
Maculan Neson, PR Univ. fédérale de Rio, Rapporteur
Tolla Pierre, PR Paris 9, rapporteur
Fdida Serge, PR Paris 6, Président
Lisser Abdel, HDR France Telecom R&D, examinateur
Pubblicazioni 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 - 6es 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”, 5e 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”, 5e 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”, these, difesa 06/26/2001, relatore Minoux, Michel, co-relazione : 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 - 2es 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”, 3e 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”, 2e 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”, 1er Congrès de la SociĂ©tĂ© Française de Recherche OpĂ©rationnelle et d'Aide Ă la DĂ©cision (ROADEF 1998), Paris, France (1998)