MILP-Evo: LLM сам проектирует и ускоряет логику MILP-солверов оптимизации

Des chercheurs ont présenté MILP-Evo, un système dans lequel un grand modèle de langage (LLM), en boucle fermée, écrit, exécute et améliore lui-même 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 dans 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 la base de leur comportement réel sur des problèmes MILP. Le résultat de chaque exécution devient un retour d'information qui guide l'évolution ultérieure du code — sans humain dans la boucle.

Dans l'article, la méthode a été testée sur la conception conjointe de deux composants du solveur à la fois : le sélecteur de coupes (cut selector) et la règle de branchement (branching rule). Ce sont précisément ces deux éléments qui déterminent en grande partie la rapidité avec laquelle le solveur trouve une solution entière.

• Deux composants sont conçus 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 se fait sur le comportement de bout en bout du solveur, et non sur une métrique proxy
• Quatre mécanismes d'évolution : sélection par résultat, réparation ciblée du code, réflexion diagnostique et maintien de la diversité de la population
• Les tests ont été réalisés sur quatre familles de benchmarks
• Le résultat est un code white-box lisible, et non un prédicteur externe de type « boîte noire »

En quoi c'est mieux que le ML classique pour les solveurs

MILP-Evo produit un code explicite et lisible au lieu d'un prédicteur externe, et c'est là la principale différence par rapport aux approches data-driven précédentes. Selon la formulation des auteurs, les politiques de machine learning entraînées sont généralement représentées comme un modèle opaque, difficile à inspecter, à adapter et à déployer. La logique manuelle du solveur, à l'inverse, est compréhensible et facile à intégrer, mais elle est écrite à la main plutôt que dérivée du retour d'information du solveur lui-même.

MILP-Evo tente de prendre le meilleur des deux mondes : la logique reste lisible à l'œil nu, mais ce n'est pas un humain qui la synthétise, mais 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 guidée par un LLM sur des composants exécutables de type white-box, évalués directement sur le comportement de bout en bout du solveur », indique le résumé du préprint MILP-Evo sur arXiv.

Dans quelle mesure cela fonctionne-t-il

Sur quatre familles de benchmarks, l'évolution de programmes pilotée par 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 compétitif « dans plusieurs configurations », et non une supériorité universelle sur les heuristiques manuelles.

Le mécanisme lui-même compte davantage : les composants obtenus sont du code ordinaire pour SCIP, qui peut être inspecté, retouché à la main et déployé dans le flux de travail standard du solveur. Cela lève le principal inconvénient des accélérateurs neuronaux — l'impossibilité de comprendre et de modifier en toute sécurité ce que le modèle a appris.

Ce que cela signifie

MILP-Evo est un exemple de plus de la façon dont les LLM passent du statut de générateurs de texte à celui de 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'information d'exécutions réelles. Pour l'optimisation, c'est un moyen d'obtenir des heuristiques à la fois rapides et transparentes, sans réglage manuel pour chaque classe de problèmes.

Questions fréquentes

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

MILP (programmation linéaire en nombres entiers mixtes) est une classe de problèmes d'optimisation à 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 du branchement — ce sont précisément elles que conçoit MILP-Evo.

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

Les approches ML précédentes représentent la politique apprise comme un prédicteur externe opaque, difficile à inspecter et à déployer. MILP-Evo produit à la place un code white-box explicite en PySCIPOpt, qu'une personne peut lire, modifier et intégrer dans le flux de travail standard de SCIP.