Technical Summary: EvoOptiGraph

Problem Statement

Automating the translation of natural language decision problems into formal mathematical optimization models (specifically Mixed-Integer Linear Programs, or MILPs) remains a significant challenge for Large Language Models (LLMs). Current approaches face two primary limitations:

1. Lack of Structural Diversity in Training Data: Existing benchmarks (e.g., NL4Opt, MAMO) cover only a narrow subset of valid optimization formulations. Data synthesis pipelines often rely on fixed templates with parameter perturbations, failing to generate the broad structural diversity required for robust generalization.
2. Static Training Pipelines: Most training setups use a frozen dataset constructed prior to model training. This decoupling prevents the system from identifying specific structural regimes where the model fails and generating new instances to target those weaknesses.

Methodology: EvoOptiGraph

The authors propose EvoOptiGraph, a weakness-driven co-evolution framework that couples data generation and model training through an explicit structural representation. The framework operates in a closed loop comprising three core components:

1. Graph-Based Structural Representation

Each MILP is represented as an attributed bipartite graph $G = (V, E, A)$:

• Nodes: One node per decision variable ($V_{var}$) and one per constraint plus a dedicated objective node ($V_{con}$).
• Edges: Connect variables to constraints/objectives where coefficients are non-zero; edge weights store the coefficient values.
• Attributes: Nodes store metadata such as variable bounds, types (integer/continuous/binary), constraint senses, and right-hand-side values.
  This representation allows for deterministic compilation into solver code (e.g., Gurobi) and supports validity-preserving genetic operations.

2. Controllable Data Generation via Graph Evolution

Instead of perturbing text or parameters, EvoOptiGraph evolves optimization instances directly on the graph space using genetic operators:

• Crossover: Exchanges compatible subgraphs between parent instances (e.g., combining a production scheduling constraint with a knapsack constraint). Cross-class crossover is permitted to increase structural diversity.
• Mutation: Operates at three levels:
  • Parameter: Perturbs coefficients, bounds, and RHS values.
  • Structural: Inserts, deletes, or modifies variables/constraints while preserving linearity.
  • Scale: Changes problem size (e.g., expanding supply/demand nodes).
• Fitness Function: Candidates are scored based on:
  • Difficulty: Derived from solver statistics (solve time, branch-and-bound nodes).
  • Diversity: Measured by Graph Edit Distance (GED) to the current population.
  • Weakness Alignment: Cosine similarity between the instance's structural features and the model's current weakness vector.

3. Two-Stage Model Training and Co-evolution Loop

The training process alternates between model fitting and data evolution:

1. Warm-up (SFT): The base LLM is supervised fine-tuned on an initial population of verified instances generated from expert seed generators.
2. Weakness Analysis: The current model is evaluated on a held-out validation set. An XGBoost classifier predicts failure based on graph-derived structural features. SHAP values are computed on error cases to generate a weakness vector ($w$) that highlights structural properties most associated with model failures.
3. Weakness-Driven RL (RLVR): The evolutionary generator is biased toward instances whose structural features align with the weakness vector ($\tilde{f}_{weak}$). The model is then updated using Reinforcement Learning with Verifiable Rewards (RLVR).
   • Rewards: A multi-stage sum based on code executability, solution feasibility, proximity to the ground-truth objective (within 10% relative error), and exact correctness.
   • Optimization: Group Relative Policy Optimization (GRPO) is used to update the policy, balancing reward maximization with KL divergence regularization against the SFT reference.

Key Contributions

1. Closed-Loop Co-evolution Framework: Unlike prior methods that separate data synthesis from model optimization, EvoOptiGraph links them via graph-level weakness analysis, allowing the training distribution to adapt dynamically to the model's evolving failure modes.
2. Controllable Graph-Based Generator: The framework performs crossover and mutation directly on attributed bipartite graphs, enabling structural-level evolution beyond simple parameter perturbations. This supports systematic exploration of diverse optimization structures.
3. Weakness-Driven Adaptation with Verifiable Feedback: The system diagnoses structural error patterns using graph features and evolves new instances specifically targeting those failures, optimizing the model with verifiable solver-based rewards.

Experimental Results

The framework was evaluated on six public benchmarks: NL4Opt, MAMO (Easy/Complex), NLP4LP, ComplexOR, and IndustryOR.

• Performance: EvoOptiGraph (using an 8B parameter backbone) achieved a macro-average Pass@1 accuracy of 78.1%, outperforming larger generalist models (e.g., GPT-4o, DeepSeek-V3), agentic methods (e.g., OptiMUS, Chain-of-Experts), and specialized fine-tuned baselines (e.g., ORLM, LLMOPT).
• Data Diversity: Instances generated by EvoOptiGraph showed a structural similarity of 66.93% to original problem types, significantly lower (indicating higher diversity) than the 93.04% similarity achieved by the text-based OptMATH method.
• Ablation Studies: Removing the co-evolution loop (SFT-only or RL-only) resulted in performance drops of 9.6% and 14.7% respectively, confirming that both the initial supervised grounding and the adaptive weakness-driven generation are critical.
• Generalization: The model demonstrated robust generalization, particularly on structurally challenging datasets like ComplexOR and MAMO-Complex, suggesting that targeted data evolution is more effective than simply scaling model size.

Significance and Claims

The paper claims that targeted data–model co-evolution is an effective strategy for improving LLMs on optimization modeling tasks. By representing MILPs as graphs and using them to drive both data generation and failure diagnosis, EvoOptiGraph creates a self-improving loop that continuously updates the training distribution to address the model's specific blind spots.

The authors emphasize that their approach demonstrates that structural data evolution can yield better results than simply increasing model scale or relying on static datasets. The framework successfully bridges the gap between the hypothesis space of valid optimization formulations and the actual capabilities of the model, providing a pathway toward more adaptive training pipelines for formal reasoning and operations research.

Limitations Acknowledged:

• The current framework is limited to MILPs and the coverage of available seed generators.
• Verification becomes computationally expensive for larger instances.
• The weakness vector serves as a practical prioritization signal rather than a causal account of errors.