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.

Abstract

We are witnessing a recent surge in the importance of machine learning, particularly deep learning, in various fields. While optimization is essential for training deep neural networks, applications of deep learning are also emerging in mathematical optimization to enrich its capabilities. This thesis focuses on the application of deep learning techniques to enhance classical approaches in operations research across different domains. The first project proposes a method for integrating learned optimization bounds within a branch-and-bound solver using a combination of reinforcement learning and decision diagrams. The challenges of combining a traditional and efficient solver with deep neural network inferences are presented, and solutions are developed and tested to solve maximum independent set problems up to 15% more quickly. The second project addresses the problem of managing a fleet of vehicles under uncertainty, using a supervised learning pipeline that adapts to fleet activity, geographic zones, and daily demand variations. A simple learning pipeline for dispatchers is presented, resulting in over 10% improvement in the fleet’s responsiveness for the partner company. The success of this project has led to extended collaboration and a new study on integrating machine learning for real-time appointment scheduling, avoiding repeated resolutions of complex vehicle routing problems. The third project proposes an unsupervised deep learning approach for generating Lagrangian factors used in the Held-Karp relaxation of the traveling salesperson problem, enabling the generation of high-quality bounds in a dedicated solver. The usefulness of machine learning in solving the traveling salesperson problem by exploiting graph structure is tested and demonstrated, with gains of up to 20% on solving time. The approach developed is general enough to be applicable to other Lagrangian relaxations. On one hand, predicting unknown values allows for the direct integration of information derived from past data into an optimization problem, resulting in more robust and adapted outcomes. On the other hand, optimization algorithms develop advanced and sophisticated techniques to enhance performance in a domain where problems are typically NP-hard and marginal gains are increasingly challenging. However, machine learning enables the discovery or replacement of heuristics by adapting to the encountered problems. These projects demonstrate the potential of deep learning in complex mathematical optimization problems and underscore the importance of incorporating learning techniques in the field of operations research. Supervised, unsupervised, and reinforcement learning methods are explored and utilized based on the nature of the encountered problems, highlighting the richness of possible approaches