MILP-Evo : un LLM conçoit et accélère lui-même la logique des solveurs d'optimisation MILP

Des chercheurs ont présenté MILP-Evo, un système dans lequel un grand modèle de langage (LLM) écrit, exécute et améliore lui-même, dans une boucle fermée, la logique des solveurs de programmation linéaire en nombres entiers mixtes (MILP). Le préprint a été publié sur arXiv en juillet 2026 : la méthode génère des composants de solveur transparents, qu'un ingénieur peut lire, vérifier et intégrer à un flux de travail standard.

Comment fonctionne la boucle fermée

MILP-Evo génère de manière itérative des programmes candidats, les charge dans le solveur open source SCIP via la bibliothèque PySCIPOpt et les évalue sur leur comportement réel face à des problèmes MILP. Le résultat de chaque exécution sert de retour d'information et pilote l'évolution suivante du code, sans intervention humaine dans la boucle.

Dans l'étude, la méthode a été éprouvée sur la conception conjointe de deux composants du solveur : le sélecteur de coupes (cut selector) et la règle de branchement (branching rule). Ces deux briques déterminent en grande partie la rapidité avec laquelle le solveur trouve une solution entière.

• Deux briques sont conçues conjointement : le sélecteur de coupes (cut selector) et la règle de branchement (branching rule)
• Les candidats sont exécutés directement dans SCIP via PySCIPOpt : l'évaluation porte sur le comportement de bout en bout du solveur, et non sur une métrique indirecte
• Quatre mécanismes d'évolution : sélection selon le résultat, réparation ciblée du code, réflexion diagnostique et maintien de la diversité de la population
• La validation a été menée sur quatre familles de benchmarks
• En sortie, du code white-box lisible, et non un prédicteur externe de type « boîte noire »

En quoi c'est préférable au ML classique pour les solveurs

MILP-Evo produit du code explicite et lisible plutôt qu'un prédicteur externe, et c'est la principale différence avec les approches data-driven précédentes. Selon les auteurs, les politiques de machine learning entraînées se présentent en général sous la forme d'un modèle opaque, difficile à inspecter, à adapter et à déployer. À l'inverse, la logique de solveur écrite à la main est compréhensible et s'intègre facilement, mais elle est rédigée manuellement et non déduite du retour d'information du solveur lui-même.

MILP-Evo tente de combiner le meilleur des deux mondes : la logique reste lisible à l'œil nu, mais elle est synthétisée non par un humain, mais par une boucle de recherche pilotée par un LLM.

«

Nous étudions si la conception automatique de la logique d'un solveur MILP peut être formulée comme une recherche en boucle fermée, pilotée par un LLM, sur des composants white-box exécutables, évalués directement sur le comportement de bout en bout du solveur », indique le résumé du préprint MILP-Evo sur arXiv.

Que valent les résultats

Sur quatre familles de benchmarks, l'évolution de programmes pilotée par un LLM trouve, dans plusieurs cas, des politiques compétitives spécialisées pour une classe de problèmes donnée. Les auteurs formulent leur conclusion avec prudence : la méthode donne un résultat competitive « dans plusieurs configurations », et non une supériorité universelle sur les heuristiques écrites à la main.

Le mécanisme compte davantage que ces chiffres : les composants obtenus sont du code ordinaire pour SCIP, que l'on peut inspecter, retoucher à la main et déployer dans le workflow standard du solveur. Cela lève le principal défaut des accélérateurs à base de réseaux de neurones : l'impossibilité de comprendre et de corriger sans risque ce que le modèle a appris.

Ce que cela signifie

MILP-Evo est un nouvel exemple de la transformation des LLM, de simples générateurs de texte en moteurs de recherche automatique de code : le modèle ne se contente pas de prédire, il écrit des composants exécutables et les améliore grâce au retour d'une exécution réelle. Pour l'optimisation, c'est un moyen d'obtenir des heuristiques rapides et transparentes, sans réglage manuel pour chaque classe de problèmes.

Questions fréquentes

Qu'est-ce que le MILP et pourquoi accélérer ses solveurs ?

Le MILP (mixed-integer linear programming, programmation linéaire en nombres entiers mixtes) désigne une classe de problèmes d'optimisation comportant des variables entières : logistique, planification, allocation de ressources. Ils sont résolus par des solveurs comme SCIP, et la vitesse de résolution dépend fortement des heuristiques de sélection des coupes et de branchement, précisément celles que conçoit MILP-Evo.

En quoi MILP-Evo diffère-t-il des accélérateurs de solveurs à base de

réseaux de neurones ?

Les approches de ML antérieures représentent la politique apprise sous la forme d'un prédicteur externe opaque, difficile à inspecter et à déployer. MILP-Evo produit à la place du code white-box explicite en PySCIPOpt, qu'un humain peut lire, modifier et intégrer au processus de travail standard de SCIP.