Résumé Technique : EvoOptiGraph

Énoncé du Problème

L'automatisation de la traduction de problèmes de décision en langage naturel vers des modèles d'optimisation mathématique formels (spécifiquement les programmes linéaires en nombres entiers mixtes, ou MILP) demeure un défi majeur pour les grands modèles de langage (LLM). Les approches actuelles font face à deux limitations principales :

1. Manque de diversité structurelle dans les données d'entraînement : Les benchmarks existants (par exemple, NL4Opt, MAMO) ne couvrent qu'un sous-ensemble étroit de formulations d'optimisation valides. Les pipelines de synthèse de données reposent souvent sur des modèles fixes avec des perturbations de paramètres, échouant ainsi à générer la large diversité structurelle requise pour une généralisation robuste.
2. Pipelines d'entraînement statiques : La plupart des configurations d'entraînement utilisent un jeu de données figé, construit avant l'entraînement du modèle. Ce découplage empêche le système d'identifier les régimes structurels spécifiques où le modèle échoue et de générer de nouvelles instances pour cibler ces faiblesses.

Méthodologie : EvoOptiGraph

Les auteurs proposent EvoOptiGraph, un cadre de co-évolution piloté par les faiblesses qui couple la génération de données et l'entraînement du modèle via une représentation structurelle explicite. Le cadre fonctionne en boucle fermée comprenant trois composantes centrales :

1. Représentation Structurelle Basée sur les Graphes

Chaque MILP est représenté comme un graphe bipartite attribué $G = (V, E, A)$ :

• Nœuds : Un nœud par variable de décision ($V_{var}$) et un par contrainte plus un nœud d'objectif dédié ($V_{con}$).
• Arêtes : Connectent les variables aux contraintes/objectifs où les coefficients sont non nuls ; les poids des arêtes stockent les valeurs des coefficients.
• Attributs : Les nœuds stockent des métadonnées telles que les bornes des variables, les types (entier/continu/binaire), les sens des contraintes et les valeurs de second membre (RHS).
  Cette représentation permet une compilation déterministe en code de solveur (par exemple, Gurobi) et supporte des opérations génétiques préservant la validité.

2. Génération de Données Contrôlable via l'Évolution de Graphes

Au lieu de perturber le texte ou les paramètres, EvoOptiGraph fait évoluer les instances d'optimisation directement dans l'espace des graphes en utilisant des opérateurs génétiques :

• Croisement (Crossover) : Échange des sous-graphes compatibles entre les instances parentes (par exemple, combiner une contrainte de planification de la production avec une contrainte de sac à dos). Le croisement inter-classes est autorisé pour accroître la diversité structurelle.
• Mutation : Opère à trois niveaux :
  • Paramétrique : Perturbe les coefficients, les bornes et les valeurs de second membre.
  • Structurelle : Insère, supprime ou modifie des variables/contraintes tout en préservant la linéarité.
  • Échelle : Modifie la taille du problème (par exemple, l'expansion des nœuds d'offre/demande).
• Fonction de Fitness : Les candidats sont évalués selon :
  • Difficulté : Dérivée des statistiques du solveur (temps de résolution, nœuds branch-and-bound).
  • Diversité : Mesurée par la distance d'édition de graphe (GED) par rapport à la population actuelle.
  • Alignement sur les Faiblesses : Similitude cosinus entre les caractéristiques structurelles de l'instance et le vecteur de faiblesse actuel du modèle.

3. Entraînement du Modèle en Deux Étapes et Boucle de Co-évolution

Le processus d'entraînement alterne entre l'ajustement du modèle et l'évolution des données :

1. Échauffement (SFT) : Le LLM de base subit un ajustement fin supervisé (Supervised Fine-Tuning) sur une population initiale d'instances vérifiées, générées à partir de générateurs de graines experts.
2. Analyse des Faiblesses : Le modèle actuel est évalué sur un ensemble de validation isolé. Un classificateur XGBoost prédit l'échec en se basant sur des caractéristiques structurelles dérivées du graphe. Les valeurs SHAP sont calculées sur les cas d'erreur pour générer un vecteur de faiblesse ($w$) qui met en évidence les propriétés structurelles les plus associées aux échecs du modèle.
3. Apprentissage par Renforcement Piloté par les Faiblesses (RLVR) : Le générateur évolutif est biaisé vers des instances dont les caractéristiques structurelles s'alignent sur le vecteur de faiblesse ($\tilde{f}_{weak}$). Le modèle est ensuite mis à jour via un Apprentissage par Renforcement avec Récompenses Vérifiables (RLVR).
   • Récompenses : Une somme multi-étapes basée sur l'exécutabilité du code, la faisabilité de la solution, la proximité avec l'objectif de vérité terrain (dans une erreur relative de 10 %) et la correction exacte.
   • Optimisation : L'optimisation de politique relative de groupe (GRPO) est utilisée pour mettre à jour la politique, équilibrant la maximisation de la récompense avec la régularisation de la divergence KL par rapport à la référence SFT.

Contributions Clés

1. Cadre de Co-évolution en Boucle Fermée : Contrairement aux méthodes antérieures qui séparent la synthèse de données de l'optimisation du modèle, EvoOptiGraph les lie via une analyse de faiblesse au niveau du graphe, permettant à la distribution d'entraînement de s'adapter dynamiquement aux modes de défaillance évolutifs du modèle.
2. Générateur de Graphes Contrôlable : Le cadre effectue le croisement et la mutation directement sur des graphes bipartites attribués, permettant une évolution au niveau structurel au-delà de simples perturbations de paramètres. Cela supporte une exploration systématique de diverses structures d'optimisation.
3. Adaptation Pilotée par les Faiblesses avec Feedback Vérifiable : Le système diagnostique les schémas d'erreur structurels en utilisant des caractéristiques de graphe et fait évoluer de nouvelles instances ciblant spécifiquement ces échements, optimisant le modèle avec des récompenses vérifiables basées sur le solveur.

Résultats Expérimentaux

Le cadre a été évalué sur six benchmarks publics : NL4Opt, MAMO (Easy/Complex), NLP4LP, ComplexOR et IndustryOR.

• Performance : EvoOptiGraph (utilisant un backbone de 8B paramètres) a atteint une précision Pass@1 moyenne macro de 78,1 %, surpassant les modèles généralistes plus larges (ex: GPT-4o, DeepSeek-V3), les méthodes agentiques (ex: OptiMUS, Chain-of-Experts) et les lignes de base spécialisées (ex: ORLM, LLMOPT).
• Diversité des Données : Les instances générées par EvoOptiGraph ont montré une similitude structurelle de 66,93 % avec les types de problèmes originaux, soit une valeur nettement plus faible (indiquant une plus grande diversité) que la similitude de 93,04 % obtenue par la méthode textuelle OptMATH.
• Études d'Ablation : La suppression de la boucle de co-évolution (SFT-uniquement ou RL-uniquement) a entraîné des baisses de performance de 9,6 % et 14,7 % respectivement, confirmant que l'ancrage supervisé initial et la génération adaptative pilotée par les faiblesses sont tous deux critiques.
• Généralisation : Le modèle a démontré une généralisation robuste, particulièrement sur les jeux de données structurellement complexes comme ComplexOR et MAMO-Complex, suggérant que l'évolution ciblée des données est plus efficace que le simple passage à l'échelle du modèle.

Signification et Revendications

L'article affirme que la co-évolution ciblée données-modèle est une stratégie efficace pour améliorer les LLM sur les tâches de modélisation d'optimisation. En représentant les MILP sous forme de graphes et en les utilisant pour piloter à la fois la génération de données et le diagnostic d'échec, EvoOptiGraph crée une boucle d'auto-amélioration qui met à jour continuellement la distribution d'entraînement pour adresser les angles morts spécifiques du modèle.

Les auteurs soulignent que leur approche démontre que l'évolution structurelle des données peut produire de meilleurs résultats que le simple élargissement de la taille du modèle ou le recours à des jeux de données statiques. Le cadre parvient à combler le fossé entre l'espace d'hypothèses des formulations d'optimisation valides et les capacités réelles du modèle, offrant une voie vers des pipelines d'entraînement plus adaptatifs pour le raisonnement formel et la recherche opérationnelle.

Limites Reconnues :

• Le cadre actuel est limité aux MILP et à la couverture des générateurs de graines disponibles.
• La vérification devient coûteuse en calcul pour les instances plus grandes.
• Le vecteur de faiblesse sert de signal de priorisation pratique plutôt que de compte rendu causal des erreurs.