Ces deux dernières années, les LLM ont fait des progrès rapides dans les domaines de la « modélisation mathématique à partir du langage naturel » et du « code de solveur à partir du langage naturel ». Les modèles sont capables de comprendre l’énoncé d’un problème, d’écrire une formulation MIP, d’appeler Gurobi ou un autre solveur, montrant ainsi qu’ils possèdent une capacité préliminaire de modélisation pour l’optimisation. Mais sur des problèmes à l’échelle industrielle réelle, cela est encore loin d’être suffisant.
La véritable difficulté ne consiste pas à traduire ligne par ligne les contraintes en expressions mathématiques, mais à concevoir un algorithme capable de traiter des instances de grande taille avec robustesse, précision et rapidité. Même un modèle MIP parfaitement correct, lorsqu’il est soumis à un solveur généraliste, peut ne pas fournir une solution de haute qualité prouvée en moins d’une heure. C’est pourquoi, dans la pratique, les ingénieurs en recherche opérationnelle doivent encore écrire des algorithmes de décomposition, de génération de colonnes, de Benders, de recherche locale, des métaheuristiques et des algorithmes hybrides combinant programmation mathématique et approches heuristiques.
Récemment, des chercheurs du MIT et d’autres institutions ont proposé FrontierOR : un benchmark d’évaluation des LLM axé sur la capacité de conception d’algorithmes d’optimisation à grande échelle.
Contrairement aux benchmarks traditionnels qui ne testent que la capacité à « modéliser » ou à « appeler un solveur », FrontierOR se concentre sur la capacité des LLM à concevoir, comme le feraient de véritables chercheurs et ingénieurs en RO, des algorithmes extensibles, de haute qualité et efficaces, adaptés à la structure de problèmes complexes.

Lien vers l’article : arxiv.org/abs/2605.25246
Page du projet : frontieror.vercel.app
Lien vers le code : github.com/Minw913/FrontierOR
Lien vers le jeu de données : SmartOR/FrontierOR
La question centrale de FrontierOR est précisément : Les grands modèles les plus puissants d’aujourd’hui peuvent-ils, à partir de problèmes réels, concevoir de manière autonome des algorithmes efficaces et compétitifs ? Peuvent-ils ne plus se contenter d’« appeler un solveur », mais plutôt, comme un expert en RO, choisir des stratégies de décomposition, heuristiques, de recherche et hybrides en fonction de la structure du problème ?
L’importance de ce travail réside dans le fait qu’il déplace l’évaluation des LLM pour la RO de « savoir écrire un modèle » vers « savoir concevoir un algorithme ». C’est aussi un seuil que les grands modèles doivent franchir pour intégrer de véritables systèmes de décision industriels.
Contexte de la recherche
De nombreux benchmarks existent déjà pour évaluer la capacité des LLM à modéliser des problèmes d’optimisation, par exemple en générant un programme mathématique à partir d’une description en langage naturel, en appelant un solveur, ou en vérifiant la réponse sur de petites instances. Ces tâches sont importantes, mais elles ont souvent du mal à répondre à une question plus proche des déploiements industriels : le modèle peut-il créer de manière proactive des chemins algorithmiques plus efficaces sur de grandes instances où les performances des solveurs ont atteint leurs limites ?
En pratique de la recherche opérationnelle, les solveurs généraux ne sont qu’un point de départ, pas une fin. Les problèmes réels présentent souvent des structures spéciales : structures de flots de réseau, décomposition temporelle, structure de tournées de véhicules, couplage inventaire/itinéraire, couplage machine/tâche en ordonnancement, couplage capacité/couverture en localisation, etc. Un bon ingénieur algorithmique exploite ces structures pour découper, approximer, relaxer, réorganiser le problème original, puis le résoudre par des méthodes heuristiques, exactes ou hybrides.
Par conséquent, un véritable benchmark pour les grands modèles en RO doit satisfaire trois conditions simultanément : les sources des problèmes doivent être assez réalistes, les instances assez grandes, et l’évaluation suffisamment rigoureuse. C’est dans ce contexte que FrontierOR est proposé : il ne s’agit pas de donner aux grands modèles une série d’« exercices d’optimisation », mais de transformer des problèmes complexes issus de la littérature RO des trente dernières années, évalués par les pairs, en tâches de conception algorithmique pouvant être évaluées automatiquement.

Tableau 1 Comparaison multidimensionnelle de FrontierOR avec des benchmarks représentatifs en RO/LLM-pour-optimisation
Méthode de recherche
Le processus de construction de FrontierOR peut être résumé en quatre étapes : sélection de problèmes dans la littérature, transformation des problèmes d’articles en composants de tâches standardisés, double contrôle de qualité automatique et par experts, puis sélection d’un sous-ensemble plus difficile « Hard ».
- Étape 1 : Sélection dans la littérature réelle. Les sources de données couvrent 180 articles publiés entre 1992 et 2025 dans plus de 20 revues de RO. Pour être retenue, une tâche doit avoir une définition claire du problème, et l’article original doit déjà démontrer la valeur pratique d’un algorithme dédié par rapport à un solveur généraliste.
- Étape 2 : Composants de tâches standardisés. Chaque article est transformé en une description du problème en langage naturel, un modèle mathématique, une implémentation de référence pour Gurobi, une solution de référence et un vérificateur de faisabilité indépendant.
- Étape 3 : Validation de qualité à deux niveaux. Tout d’abord, une vérification automatique par validation croisée contrôle la cohérence entre la solution de référence Gurobi et le vérificateur de faisabilité. Ensuite, 15 experts en RO effectuent plusieurs tours de révision pour vérifier la cohérence entre le modèle, la description, le code et le vérificateur.
- Étape 4 : Sélection du sous-ensemble Hard. Sur les 180 tâches, 50 plus difficiles sont sélectionnées, se concentrant sur les scénarios présentant une explosion combinatoire, une plus grande échelle, des contraintes plus couplées, et où Gurobi ne peut pas prouver l’optimalité dans un budget d’une heure.

Figure 1 Vue d’ensemble du benchmark FrontierOR : catégories de problèmes, domaines d’application, échelle des instances et processus de construction
Protocole d’évaluation
Le processus d’évaluation met également l’accent sur les capacités de bout en bout. Le modèle génère d’abord un programme algorithmique complet basé sur la description de la tâche en langage naturel. Le programme est d’abord pré-filtré sur de petites instances pour la faisabilité d’exécution, la faisabilité du problème et la qualité : s’il dépasse le temps imparti, est infaisable, ou présente un écart de plus de 10 % par rapport à la solution Gurobi sur la petite instance, il n’est pas évalué sur les grandes instances.
Après ce pré-filtrage, le programme est exécuté sur plusieurs grandes instances de chaque tâche et comparé à la solution de référence Gurobi validée par les experts. FrontierOR utilise quatre métriques : le taux d’exécution (Execution rate), la faisabilité (Feasibility), la qualité de la solution (Solution quality) et l’efficacité qualité-temps (QTE). La QTE est la plus stricte : seules les solutions dont la valeur objective a un écart relatif par rapport à la solution de référence Gurobi inférieur ou égal à 1 %, ou qui surpassent Gurobi, sont considérées comme réussies.

Figure 2 Processus d’évaluation en deux étapes de FrontierOR : pré-filtrage sur petites instances, évaluation de la qualité et de la vitesse sur grandes instances
Résultats expérimentaux
One-shot : la faisabilité d’exécution approche la limite supérieure
Dans le cadre one-shot, le modèle doit générer un programme algorithmique complet à partir de zéro. Il peut effectuer un débogage limité basé sur les erreurs d’exécution, mais ne peut pas réécrire l’algorithme de manière itérative en fonction des retours d’évaluation. Ce cadre évalue la capacité globale du modèle à lire, modéliser, concevoir un algorithme et coder en une seule fois.
Les résultats montrent que la faisabilité d’exécution des modèles les plus puissants est déjà très élevée. Par exemple, GPT-5.3-Codex atteint un taux d’exécution de 0,98 sur l’ensemble complet (Full), Gemini 3.1 Pro et Claude Opus 4.6 atteignent tous deux 0,93. Cela montre que pour les modèles de pointe, « le code peut-il s’exécuter » n’est plus le principal goulot d’étranglement.
Mais être exécutable ne signifie pas être capable de résoudre. La faisabilité (Feasibility), la qualité de la solution (Solution quality) et la QTE restent significativement inférieures au taux d’exécution. En d’autres termes, les grands modèles savent déjà écrire des programmes d’optimisation formellement complets, mais il est encore difficile pour ces programmes de rester faisables, proches de l’optimalité et plus rapides que Gurobi à l’échelle industrielle.
En termes de hiérarchie globale, les modèles de pointe surpassent significativement les autres modèles grand public sur l’ensemble complet (Full) et le sous-ensemble Hard. Sur l’ensemble FrontierOR, la faisabilité des modèles de pointe se concentre autour de 0,60–0,62, tandis que celle des autres modèles grand public se situe entre 0,18 et 0,42. L’écart persiste sur le sous-ensemble Hard : les modèles de pointe sont entre 0,49 et 0,64, les autres modèles grand public descendent à 0,13–0,37.
Le sous-ensemble Hard accentue encore les écarts de capacité algorithmique entre les modèles de pointe eux-mêmes. Sur l’ensemble complet, la QTE des trois modèles de pointe se situe dans une fourchette étroite de 0,25 à 0,31, semblant proche. Mais sur le sous-ensemble Hard, la QTE de Claude Opus 4.6 atteint encore 0,32, tandis que celle de GPT-5.3-Codex descend à 0,18, une différence proche du double. Le sous-ensemble Hard devient donc un véritable « point de séparation des compétences en ingénierie algorithmique ».

Tableau 2 Résultats de l’évaluation one-shot de FrontierOR : Taux d’exécution, faisabilité, qualité de solution et QTE sur l’ensemble complet (Full) et le sous-ensemble Hard
Divergence dans le choix des algorithmes
L’équipe de recherche a ensuite analysé les méthodes de résolution utilisées par les programmes générés par les modèles, les classant en cinq catégories : appel pur à un solveur, décomposition, heuristique constructive, recherche locale/métaheuristique, et méthodes hybrides programmation mathématique-heuristique. Cette analyse est cruciale car elle révèle directement si le modèle possède une véritable conscience de la conception algorithmique.
Les résultats montrent que les modèles plus faibles dépendent fortement des appels purs à un solveur. Par exemple, environ 99 % des programmes de LLaMA-4-Maverick sont des appels monolithiques à un solveur, ce qui revient essentiellement à déléguer le problème à un solveur généraliste. En revanche, la distribution des méthodes de Claude Opus 4.6 est la plus équilibrée : environ 37 % d’appels purs à un solveur, 27 % de recherche locale/métaheuristique, 27 % d’hybrides programmation mathématique-heuristique.
Plus important encore, les méthodes autres que l’appel pur à un solveur présentent globalement un avantage sur la métrique QTE. Cela signifie que la « diversité des méthodes » est en soi une source de compétitivité : plus un modèle est capable de choisir des algorithmes de décomposition, heuristiques et hybrides en fonction de la structure du problème, plus il a de chances d’obtenir à la fois qualité et vitesse sur les grandes instances.

Figure 3 Distribution des méthodes de résolution utilisées par les programmes générés par différents modèles et analyse des modes d’échec
Migration des modes d’échec : de « ne sait pas modéliser » à « ne cherche pas assez profondément »
L’analyse des modes d’échec montre qu’avec l’amélioration des capacités des modèles, l’emplacement des erreurs se déplace systématiquement vers l’arrière. Les modèles plus faibles échouent principalement lors des étapes préliminaires : conception du modèle mathématique, spécification des contraintes, schéma d’entrée/sortie. Les modèles plus forts commettent nettement moins d’erreurs sur ces aspects fondamentaux ; le nouveau goulot d’étranglement se déplace vers la profondeur et la qualité de la recherche heuristique.
Cela ressemble beaucoup au parcours d’apprentissage d’un ingénieur algorithmique humain. Les débutants commettent d’abord des erreurs de modélisation : définition floue des variables, contraintes manquantes, incohérences entrée/sortie. Les ingénieurs plus expérimentés font moins d’erreurs basiques, mais sont confrontés à des problèmes plus difficiles : la stratégie de recherche est-elle assez puissante ? Le voisinage est-il bien conçu ? La relaxation et la réparation peuvent-elles concilier vitesse et qualité ?
Ainsi, FrontierOR ne nous dit pas seulement « qui a le meilleur score », mais aussi « où se situe le goulot d’étranglement des capacités ». Cela est particulièrement important pour la conception des prochaines générations de systèmes LLM-pour-RO : les futures avancées ne viendront pas nécessairement de modèles meilleurs pour écrire des formules, mais plutôt de systèmes meilleurs pour la recherche, pour combiner des compétences algorithmiques et pour utiliser les retours d’expérience pour s’améliorer.
Auto-évolution
La génération en une seule fois n’est que la première étape. Dans la réalité, la conception d’algorithmes n’est jamais définitive ; c’est un processus itératif d’exécution, d’analyse des échecs, de modification des stratégies et de ré-exécution. C’est pourquoi FrontierOR évalue en plus trois cadres d’auto-évolution au moment du test : OpenEvolve, EoH et CORAL.
L’expérience sélectionne les 40 % de tâches les plus difficiles du sous-ensemble Hard comme jeu de test pour l’auto-évolution, en utilisant le programme généré en one-shot par GPT-5.3-Codex comme semence initiale. Chaque cadre est limité à 30 programmes candidats, le meilleur résultat final étant considéré comme l’état final. Cela garantit que les différences proviennent principalement du mécanisme de recherche, et non des programmes initiaux.
Les résultats sont très impressionnants : sous les trois cadres d’auto-évolution, le meilleur programme candidat surpasse significativement la génération one-shot sur toutes les métriques. La QTE passe de 0,15 en one-shot à un maximum de 0,50. Cela signifie que sur les tâches les plus difficiles, près de la moitié des grandes instances peuvent désormais être traitées par un algorithme généré par LLM satisfaisant simultanément les deux conditions « qualité proche de Gurobi » et « vitesse non inférieure à Gurobi ».
Parmi eux, CORAL, avec son mécanisme de mémoire partagée multi-agents, obtient l’amélioration la plus stable, avec une QTE de 0,50 ; OpenEvolve suit de près avec une QTE de 0,49 ; EoH apporte également une amélioration notable, mais avec une performance plus variable, avec une QTE de 0,33.

Tableau 3 Performance des trois cadres d’auto-évolution au moment du test sur les tâches les plus difficiles : La QTE maximale passe de 0,15 à 0,50
En observant de plus près les trajectoires d’évolution, on observe un phénomène révélateur : la dimension de la vitesse peut souvent surpasser la ligne de base Gurobi dans les 5 premières tentatives, tandis que la dimension de la qualité de la solution est beaucoup plus difficile à améliorer. La raison n’est pas difficile à comprendre : pour qu’un algorithme soit plus rapide, il suffit souvent d’adopter une heuristique constructive légère ; mais pour être à la fois plus rapide et proche de l’optimum global, il faut des voisinages plus fins, des stratégies de réparation, de relaxation et un contrôle de la recherche plus élaborés.
Cela montre que l’auto-évolution des LLM ne consiste pas simplement à « essayer le code plusieurs fois ». Une auto-évolution véritablement efficace doit être capable de mémoriser les échecs passés, d’identifier les goulots d’étranglement de performance, d’ajuster dynamiquement la direction de la recherche et de faire des compromis structurés entre vitesse et qualité.

Figure 4 Trajectoires d’évolution bidimensionnelles qualité-vitesse des trois cadres d’auto-évolution : La vitesse est facile à améliorer en premier, la qualité est plus difficile à augmenter
Applications futures
La valeur de FrontierOR ne se limite pas à classer les modèles, elle fournit également des orientations claires pour le développement des prochaines générations de systèmes d’optimisation intelligents. Si les grands modèles pouvaient comprendre de manière stable les besoins métier réels, identifier les structures d’optimisation, appeler ou combiner les compétences algorithmiques appropriées, et s’améliorer grâce aux retours d’exécution, ils pourraient alors devenir des « ingénieurs algorithmiques IA » au sein des systèmes de décision industriels.
Dans un scénario de chaîne d’approvisionnement, un tel système pourrait générer automatiquement des algorithmes de planification et de routage adaptés à des échelles spécifiques, en fonction des commandes, des entrepôts, des stocks, du réseau de transport et des exigences de délais. Dans les systèmes énergétiques, il pourrait concevoir des stratégies de résolution rapide par approximation pour la gestion du réseau électrique, le stockage d’énergie et l’équilibrage de la charge. Dans les systèmes de transport et urbains, il pourrait générer des algorithmes d’optimisation déployables en temps réel pour répondre à la demande dynamique, la propagation des congestions et les contraintes de ressources.
En allant plus loin, FrontierOR suggère également la forme future de l’optimisation agentique : le LLM ne serait plus seulement un générateur de code, mais un agent intelligent de conception d’algorithmes, capable d’utiliser une bibliothèque de compétences, d’appeler des vérificateurs, d’exécuter des expériences, d’attribuer les erreurs et d’explorer activement sous un budget limité.
Perspectives
- Construire une bibliothèque de compétences en conception d’algorithmes de RO. Capitaliser les stratégies courantes comme la décomposition, la relaxation, la génération de colonnes, la recherche locale, la réparation, le redémarrage, la résolution hybride, etc., en modules de compétences pouvant être recherchés, combinés et exécutés, permettant à l’agent de choisir automatiquement des modèles algorithmiques en fonction de la structure du problème.
- Développer des vérificateurs/évaluateurs plus fiables. L’évaluateur ne doit pas seulement vérifier la faisabilité, mais aussi identifier quel type de contrainte provoque l’échec, quel type de recherche locale stagne, transformant ainsi les retours d’exécution en orientation pour la conception suivante.
- Améliorer la capacité de planification du budget dans l’auto-évolution. Sur des instances à grande échelle, chaque évaluation est coûteuse. Les futurs systèmes devront apprendre quand explorer de nouvelles structures, quand affiner les paramètres, quand arrêter des directions inefficaces.
- Promouvoir l’intégration profonde des LLM avec les solveurs d’optimisation traditionnels. La direction la plus prometteuse n’est peut-être pas « le LLM remplace le solveur », mais plutôt le LLM se concentre sur la découverte de structures et la conception d’algorithmes, tandis que le solveur traditionnel se charge de l’optimisation locale précise et de la vérification fiable.
En résumé, FrontierOR dresse la première cartographie systématique des capacités d’ingénierie algorithmique en RO pour les grands modèles : ils sont déjà capables d’écrire des algorithmes d’optimisation partiellement compétitifs, mais ce qui détermine vraiment leur plafond n’est plus la syntaxe du code ou la traduction de formules, mais la capacité à découvrir les structures, à concevoir des recherches et à s’auto-évoluer.
Si la recherche précédente sur les LLM-pour-RO répondait à la question « Les grands modèles savent-ils modéliser ? », FrontierOR commence à poser une question plus difficile et plus réaliste : Les grands modèles peuvent-ils devenir de véritables concepteurs d’algorithmes ?
Références : arxiv.org/abs/2605.25246
Cet article provient du compte WeChat « Xin Zhi Yuan » (新智元), auteur : Xin Zhi Yuan ; édité par : LRST






