Apprentissage d'heuristiques pour la résolution de problèmes d'optimisation combinatoire dans les réseaux
08/12/2023 à 14h00
M.Chen DANG présente ses travaux en soutenance le 08/12/2023 à 14h00
À l'adresse suivante : Université Paris Dauphine-PSL Pl. du Maréchal de Lattre de Tassigny, 75016 Paris Salle A701
En vue de l'obtention du diplôme : Doctorat en Informatique
La soutenance est publique
Titre des travaux
Apprentissage d'heuristiques pour la résolution de problèmes d'optimisation combinatoire dans les réseaux
École doctorale
École doctorale Dauphine SDOSE
Équipe de recherche
UMR 7243 - Laboratoire d’Analyse et de Modélisation de Systèmes d’Aide à la Décision
Section CNU
27 - Informatique
Directeur(s)
Mme Cristina BAZGAN
Membres du jury
| Nom | Qualité | Établissement | Rôle |
|---|---|---|---|
| Mme Cristina BAZGAN | Professeur des universités | UNIVERSITE PARIS DAUPHINE - PSL | Directrice de thèse |
| M. Morgan CHOPIN | Ingénieur de recherche | Orange Labs | Co-encadrant de thèse |
| Mme Hind CASTEL-TALEB | Professeur | TSP-Telecom SudParis | Rapporteure |
| M. Frédéric SAUBION | Professeur des universités | Université d'Angers | Rapporteur |
| M. Frédéric GIROIRE | Directeur de recherche, CNRS | Université Côte d'Azur | Examinateur |
| M. Bernard FORTZ | Professeur | Université de Liège, HEC | Examinateur |
| M. Tristan CAZENAVE | Professeur des universités | UNIVERSITE PARIS DAUPHINE - PSL | Examinateur |
| M. Pierre-Henri WUILLEMIN | Maître de conférences | LIP6 - Sorbonne Université | Examinateur |
Résumé
Cette thèse examine les problèmes d'optimisation dans l'ingénierie de traffic des réseaux de télécommunications. En particulier, nous avons étudié le problème de minimisation de la congestion dans les réseaux IP reposant sur le protocole de routage au plus court chemin (OSPF, IS-IS) d'une part et le segment routing d'autre part. Dans un premier temps, nous introduisons de nouvelles méthodes pour améliorer la performance des réseaux. La principale contribution de la thèse est l'application de la méthode de recherche Monte Carlo Nested Rollout Policy Adaptation (NRPA) au problème d'optimisation des métriques (OSPF Weight Setting). L'approche proposée s'adapte bien à la taille de l'instance et peut être facilement étendue pour prendre en compte des contraintes ou des critères d'optimisation supplémentaires (délai bout en bout, unicité des chemins de routage, etc...). En outre, la thèse présente une version améliorée de NRPA, appelée Meta-NRPA, qui utilise la théorie de l'arrêt optimal pour mieux guider la recherche de NRPA. De plus, nous présentons plusieurs techniques exploratoires pour NRPA permettant une exploration plus efficace de l'espace des solutions. Nos expérimentations confirment l'amélioration significative des performances de NRPA. Dans un deuxième temps, la thèse introduit un algorithme Hierarchical Shortest Path Routing (HSPR), une version adaptée de l'algorithme Customizable Contraction Hierarchy (CCH). Il accélère significativement la simulation des protocoles de routage au plus court chemin comparé aux méthodes traditionnelles basées sur l'algorithme de Dijkstra. Nous l'avons combiné avec l'algorithme Meta-NRPA pour résoudre le problème OSPF Weight Setting. Les résultats obtenus montrent une amélioration substantielle des performances de Meta-NRPA, surtout dans les grands réseaux. Enfin, nous étudions également plusieurs heuristiques pour le problème d'optimisation de routage par segments, en se concentrant sur le Waypoint Optimization problem. Nous combinons une approches basée sur la recherche locale et la décomposition arborescente pour guider efficacement la recherche. Nous proposons également d'autres approches basées sur le reinforcement learning et évaluons leur efficacité à travers une série d'expériences approfondies sur des données réelles et synthétiques.