Les grands modèles de langage (LLM) comme assistants guidés pour la résolution de problèmes d’optimisation combinatoire

Abstract

Ce mémoire porte sur l’évaluation des grands modèles de langage, ou Large Language Models (LLM), comme outils d’assistance à la résolution de problèmes d’optimisation combinatoire. Dans les systèmes industriels et logistiques, les décisions liées à la localisation, à la couverture, à la planification de production ou au routage nécessitent des méthodes rigoureuses permettant de produire des solutions faisables, performantes et vérifiables. L’émergence des LLM ouvre de nouvelles perspectives pour l’aide à la modélisation, la génération de code et la proposition de méthodes de résolution. Cependant, leur fiabilité reste une question centrale, car une réponse bien formulée peut contenir des erreurs de raisonnement, de calcul ou de faisabilité. L’objectif de ce travail est d’analyser dans quelle mesure les LLM peuvent assister la résolution de problèmes d’optimisation combinatoire, tout en identifiant leurs limites. L’étude repose sur une démarche expérimentale en deux phases. La première phase évalue les modèles de manière relativement autonome, afin d’observer leur capacité à comprendre les problèmes, proposer une méthode et produire une solution. La deuxième phase introduit un guidage heuristique, dans lequel les modèles doivent appliquer une méthode imposée et vérifier les résultats obtenus. Les expérimentations portent principalement sur trois problèmes classiques : le problème du p-médian, le Set Covering Problem et l’Uncapacitated Lot Sizing Problem. Les réponses des LLM sont évaluées à partir de plusieurs indicateurs, notamment la faisabilité, la valeur objective, le gap par rapport à une référence, la fiabilité, la correction de l’implémentation et l’amélioration par rapport à la phase initiale. Les résultats montrent que les LLM peuvent parfois bénéficier d’un guidage heuristique, notamment pour améliorer la faisabilité ou structurer la résolution. Toutefois, leurs performances restent instables selon les modèles et les problèmes étudiés. Ce travail confirme donc que lesLLMne peuvent pas être considérés comme des solveurs autonomes fiables, mais qu’ils peuvent jouer un rôle d’assistants guidés, à condition que leurs résultats soient systématiquement vérifiés par des méthodes externes.