Thèse en apprentissage d'heuristiques pour la résolution de problèmes d'optimisation combinatoire dans les réseaux - H/F

Description de l'offre

about the role

L'objectif de cette thèse est de fournir de nouvelles méthodes d'apprentissage afin d'obtenir des heuristiques qui améliorent l'efficacité des algorithmes d'optimisation combinatoire. Un résultat récent [6] tend à montrer que l'apprentissage par renforcement est une technique prometteuse pour concevoir des algorithmes gloutons pour des problèmes de graphes comme le Vertex Cover , Max Cut ou TSP . Une question qui se pose alors naturellement, serait d'étendre ces résultats dans le contexte des problèmes d'optimisation dans les réseaux. Par exemple, un problème central en Traffic Engineering est la détermination de poids ou métriques administratives dans un réseau IP qui induisent un routage au plus court chemin générant un minimum de congestion [4].  Formellement, le problème consiste à déterminer un ensemble de poids à attribuer aux liens et un ensemble de chemins de routage induits par ces poids de telle sorte que (i) pour chaque paire origine-destination du réseau, il y ait un unique plus court chemin relatif aux poids identifiés et (ii) que la congestion du réseau soit minimale. Actuellement, les algorithmes que l'on trouve dans la littérature ne permettent de résoudre ce problème que sur de petites instances de quelques dizaines de noeuds.  Cela est dû en partie à la difficulté de concevoir des heuristiques « à la main » permettant de guider efficacement la résolution.  Par conséquent, ce problème est un bon candidat pour l'application de techniques de ML afin d'obtenir des heuristiques efficaces ou, au moins, pour aider à les concevoir (comme suggéré dans [6]).  D'un point de vue plus théorique, on notera qu'il s'agit d'un problème de routage qui appartient à la classe plus large des problèmes d'optimisation inverse.  Cela suggère que les techniques hybrides ML/OC obtenues pour résoudre ce problème particulier peuvent conduire à une approche plus générale pour résoudre des problèmes de cette catégorie.  De plus, le modèle d'apprentissage développé devra prendre comme entrée à la fois un graphe et une matrice de trafic.  La question de trouver un plongement approprié pour ces deux entrées reste ouverte.

 

Par ailleurs, une de nos approches pour résoudre ce problème consiste à utiliser un algorithme de programmation dynamique basé sur la notion de décomposition arborescente [3].   Plus généralement, le calcul d'une décomposition de graphe (décomposition arborescente ou de branchement) servant de support à un algorithme de programmation dynamique est une méthode standard de conception d'algorithmes exacts.  Leur efficacité dépend alors fortement de la "qualité" de la décomposition fourni, et il est généralement NP-difficile de trouver la meilleure décomposition. Ainsi, une piste de recherche intéressante à explorer serait d'appliquer le ML afin de produire des décompositions de bonnes qualités. Il existe certains travaux dans cette direction [1], mais l'apprentissage d'une heuristique qui construit une décomposition de graphe appropriée est encore largement inexploré, en particulier dans le contexte des problèmes d'optimisation dans les réseaux.

about you

Master en informatique avec une spécialisation dans le domaine de l'intelligence artificielle.

- Une solide formation en informatique et plus particulièrement en intelligence artificielle et techniques de machine learning (apprentissage par renforcement, apprentissage profond, etc..).

- Connaissance des méthodologies et algorithmes d'optimisation combinatoire, de la programmation mathématique et de la théorie des graphes.

- Expérience de programmation dans un ou plusieurs des langages suivants : Python, C, C++...

- Connaissance d'au moins un framework de machine learning (TensorFlow, PyTorch,..).

additional information

Vous rejoindrez l'un des projets phares de la stratégie d'Orange, au sein d'un département pluridisciplinaire et opérationnel, en forte interaction avec des équipes de recherche reconnues dans le domaine. Vous interagirez également avec le LAMSADE (U. Paris-Dauphine) et le LIP6 (Université de la Sorbonne) qui sont deux centres de recherche académique reconnus dans le domaine de l'optimisation combinatoire et de l'intelligence artificielle, respectivement.

department

Vous rejoindrez l'équipe MORE (Mathematical Models for Optimization and peRformance Evaluation) de l'entité DATA-IA (Orange Gardens, Châtillon) qui est composée de chercheurs, de doctorants et d'ingénieurs logiciels. L'équipe travaille sur le développement de modèles mathématiques pour évaluer les performances ou résoudre des problèmes d'optimisation combinatoire dans les réseaux.

contract

Thèse