Évaluation du potentiel des grands modèles de langage (LLM) pour résoudre des problèmes d’optimisation combinatoire

Abstract

Ce mémoire s’intéresse à l’évaluation des grands modèles de langage, ou Large Language Models (LLM), dans le contexte de l’optimisation combinatoire appliquée à la logistique et à la gestion de production. L’objectif principal est d’analyser dans quelle mesure des LLM grand public peuvent être utilisés comme outils d’aide à la résolution de problèmes d’optimisation, en particulier lorsqu’ils sont sollicités par un utilisateur non expert. L’étude porte sur trois problèmes classiques : le Uncapacitated P-Median Problem (UPMP), le Set Covering Problem (SCP) et le Uncapacitated Lot Sizing Problem (ULS). Ces problèmes ont été choisis pour leur importance en recherche opérationnelle, leur lien direct avec des décisions industrielles et logistiques, ainsi que pour la disponibilité d’instances de benchmark et de solutions de référence. Cinq LLM ont été évalués : ChatGPT 5.3, Gemini 3, DeepSeek, Grok 4 et Claude Sonnet 4.6. Le travail commence par une présentation des notions liées à l’intelligence artificielle, à l’IA générative et aux LLM, puis introduit les principes du prompt engineering. Un framework de conception de prompts est ensuite proposé afin de structurer les demandes soumises aux modèles. Ce framework repose notamment sur la formulation en anglais, la spécification d’un rôle d’expert, l’interdiction de reproduire des solutions optimales connues, la décomposition des tâches, la demande d’un format de sortie précis et la mesure du temps de réponse. La première phase expérimentale évalue les LLM comme solveurs autonomes. Les modèles reçoivent la description du problème et les données associées, sans solveur externe ni méthode de résolution imposée. Les réponses produites sont ensuite vérifiées à l’aide de scripts Python et analysées dans Excel. Plusieurs indicateurs sont utilisés, notamment Solution Quality, Optimality First Iteration, Capability, Feasibility, Reliability, Stability, Improve Learning, Query Efficiency, Response Time et GAP. Les résultats montrent que les LLM peuvent produire des réponses structurées et parfois des solutions de bonne qualité, mais que leurs performances varient fortement selon le modèle, le problème et la taille des instances. Claude Sonnet 4.6 se distingue globalement par sa qualité de solution, sa faisabilité et sa fiabilité, notamment sur le p-median et le ULS. Grok 4 obtient de très bons résultats sur le SCP et présente une bonne capacité d’amélioration dans certains cas. ChatGPT 5.3 est souvent le plus rapide, mais ses solutions nécessitent une vérification attentive. Gemini 3 et DeepSeek montrent des performances plus irrégulières, en particulier en matière de faisabilité et de fiabilité. Cette étude met en évidence une limite importante des LLM utilisés comme solveurs autonomes : une réponse bien formulée ne garantit pas une solution correcte. Les modèles peuvent commettre des erreurs de calcul, produire des solutions infaisables ou annoncer à tort une solution optimale. Ainsi, les LLM ne peuvent pas remplacer les méthodes classiques d’optimisation ni les solveurs spécialisés. En revanche, ils peuvent constituer des assistants utiles pour formuler un problème, proposer une première solution, expliquer une démarche ou accompagner un utilisateur dans un processus de résolution, à condition que leurs résultats soient systématiquement vérifiés.