Apprentissage Profond en Optimisation Combinatoire : Apprentissage de Bornes et Résolution de Problèmes de Transport

Nous assistons récemment à une montée en puissance de l’importance de l’apprentissage automatique et particulièrement de l’apprentissage profond dans de nombreux domaines. Si l’optimisation est indispensable à l’entraînement des réseaux de neurones profonds, des applications de l’apprentissage profond font à leur tour apparition en optimisation mathématique afin d’en enrichir les possibilités. Cette thèse se concentre sur l’application des techniques d’apprentissage profond pour l’amélioration d’approches classiques de recherche opérationnelle dans différents domaines. Le premier projet propose une méthode d’intégration de bornes d’optimisation apprises à l’intérieur d’un solveur branch-and-bound, en utilisant une combinaison d’apprentissage par renforcement et de diagrammes de décision. Les difficultés d’une association d’un solveur classique et performant à des inférences de réseaux de neurones profonds sont présentés et des solutions sont developpées et testées afin de résoudre jusqu’à 15% plus rapidement des problèmes de stable maximum. Le deuxième projet aborde le problème de la gestion d’une flotte de véhicules sous incertitude, en utilisant une méthodologie basée sur de l’apprentissage supervisé qui s’adapte à l’activité de la flotte, à la zone géographique et à la variation des demandes quotidiennes. Une méthode simple d’apprentissage au service de répartiteurs est présentée et permet une amélioration de plus de 10% de la réactivité de la flotte de l’entreprise partenaire. Le succès de ce projet a donné lieu à une collaboration prolongée et à une nouvelle étude d’intégration d’apprentissage automatique pour la prise de rendez-vous en temps réel évitant les résolutions répétées d’un problème de tournée de véhicule complexe. Le dernier projet propose une approche d’apprentissage profond non-supervisé pour la génération de facteurs lagrangiens utilisés dans la relaxation de Held et Karp du problème très général de voyageur de commerce, afin de générer rapidement des bornes performantes dans un solveur dédié. L’intérêt de l’apprentissage machine dans la résolution d’un problème de voyageur de commerce en exploitant la structure de graphe est testée et démontrée, aboutissant à des réductions du temps de résolution de l’ordre de 20%. L’approche développée est suffisamment générale pour être transposable à d’autres relaxations lagrangiennes. Les apports de l’apprentissage profond dans le domaine de l’optimisation explorés dans cette thèse se manifestent principalement à travers deux types de contributions : d’une part, la prédiction de valeurs inconnues permet d’intégrer directement les informations tirées de données passées dans un problème d’optimisation dont le résultat sera plus robuste et adapté ; d’autre part, les algorithmes d’optimisation développent des techniques avancées et sophistiquées afin de gagner en performance dans un domaine ou les problèmes sont généralement NP-difficiles et les gains de plus en plus marginaux, mais l’apprentissage automatique permet de découvrir ou remplacer des heuristiques en s’adaptant notamment aux problèmes rencontrés. Ces projets démontrent le potentiel de l’apprentissage profond dans des problèmes d’optimisation mathématique complexes, et soulignent l’importance de l’incorporation des techniques d’apprentissage dans le domaine de la recherche opérationnelle. Des méthodes d’apprentissage supervisé, non-supervisé et par renforcement sont explorés et utilisés en fonction de la nature de problèmes rencontrées, mettant en évidence la richesse des approches possibles.