FormuEvo: LLM-Guided Evolution for Discovering Solver-Efficient Mixed-Integer Programming Formulations

AI summary

Overview

Research area: Automated mathematical modeling and optimization — specifically, using large language models (LLMs) to design mixed-integer programming (MIP) formulations that are not just correct but fast to solve.

Technical level: Advanced. The paper assumes familiarity with MIP, branch-and-bound, LP relaxation, presolving, and evolutionary search. The framing and motivation are accessible, but the results tables require optimization background.

Scope: The paper introduces FormuEvo, an LLM-guided evolutionary framework that searches over the symbolic space of executable MIP modeling programs to discover formulations that minimize downstream solver runtime, evaluated on five classical optimization benchmarks plus two novel problem settings.

What This Paper Is About

A single optimization problem can have many mathematically equivalent MIP formulations that all yield the same optimal solution but differ enormously in how fast a solver like Gurobi can find it. Existing LLM-based modeling tools are trained to produce correct and executable formulations, but they ignore formulation strength, so their outputs are often naive textbook models that scale poorly.

This paper reframes formulation design as a search problem: rather than generating one formulation in a single pass, FormuEvo evolves a population of candidate formulations over generations, using solver runtime as the fitness signal and fine-grained solver statistics as guidance.

Key Contributions

1. FormuEvo framework: An LLM-guided evolutionary framework that treats MIP formulation design as evolutionary optimization over the symbolic space of MIP formulations, represented as executable modeling programs, iterated through LLM-driven crossover, mutation, and repair operations.

2. Solver-informed diagnosis: A mechanism in which the diagnostic LLM converts fine-grained solver statistics (presolving outcomes, relaxation quality, branching dynamics) into structured, interpretable "verbal gradients" that attribute computational bottlenecks to specific structural properties and propose targeted improvements.

3. Structured memory with distillation: A memory library that stores experience as entries with three fields — condition, strategy, and effect — abstracted by a reflector LLM. A distiller LLM later summarizes accumulated memory into problem-agnostic knowledge, enabling zero-shot transfer to unseen problems and bootstrapping of smaller LLMs.

4. Empirical discovery of non-obvious formulations: FormuEvo finds formulations that outperform expert-designed and LLM-based baselines, accelerating MIP solvers by up to 5.5 times; the best discovered formulations are reported in the appendix.

Main Findings

• Up to 5.5x solver acceleration: Across diverse linear and non-linear problems, FormuEvo discovers formulations that significantly outperform both expert-designed formulations and existing LLM-based approaches.

• Theory-tight formulations can be practically disastrous: On TSP, the human-designed MCF-RLT formulation achieves the theoretically tightest known relaxation bound but fails completely on Hard instances (0/100 solved, 600.0570 seconds). FormuEvo instead achieves 3.9469 seconds on TSP Hard (+52.6%), solving 100/100 instances with 80/100 wins.

• Correctness-oriented LLMs produce weak formulations: ORLM and StepORLM generate correct and executable formulations on standard MILPs but their outputs largely remain naive textbook formulations that scale poorly. On JSSP Easy, ORLM reaches the 600-second time limit (600.0012) with 0/100 solved. Both approaches also fail to produce valid formulations for the novel NNV and IMO problems.

• Local strengthening has a ceiling; structural redesign does not: EvoCut, which generates cutting planes on a fixed model, yields only moderate improvements. On BPP it remains weaker than both VPSolver and FormuEvo because BPP's bottleneck lies in its assignment structure rather than LP relaxation strength. On QAP, the standard quadratic formulation already defines a Birkhoff polytope representing the convex hull, and EvoCut achieves no improvement from strengthening cuts. FormuEvo instead discovers structural reformulations such as alternative linearizations and variable extension.

• Consistent wins across problem families: FormuEvo attains the best runtime on the majority of instances across nearly all benchmarks. Examples: TSP Easy 0.1410 (+54.2%, 87/100 wins), TSP Medium 0.5640 (+44.0%, 79/100), JSSP Hard 15.4237 (+12.7%, 41/100), BPP Hard 0.8384 (+41.9%, 55/100), CFLP Hard 44.3447 (+25.4%, 71/100), QAP Hard 34.5034 (+8.8%, 53/100).

• Strong results on problems with little human prior work: On neural network verification, FormuEvo reaches 21.4139 seconds (+68.3%) with 78/100 wins and 86/100 solved, versus the standard formulation at 69.5200 (71/100 solved) and EvoCut at 67.6093 (73/100 solved). On the IMO 2025 Problem 6 derived challenge, FormuEvo achieves 17.9341 seconds (+82.0%), winning all 4/4 instances and solving all 4/4, versus 114.0912 for the standard formulation and 99.4400 for EvoCut (each 3/4 solved).

• Both key components matter: Ablations on TSP Hard show FormuEvo at 3.9469 seconds versus 4.6649 without memory and 6.5207 without diagnosis. On JSSP Hard, FormuEvo is 15.4237 versus 16.3223 without memory and 18.0159 without diagnosis. The diagnosis mechanism provides the directional signal, while memory reuse improves search efficiency.

• Distilled knowledge transfers to smaller models: Using GPT-5.4-nano on unseen problems, evolution without transfer converges substantially more slowly and ends at higher runtime, struggling to improve on baseline formulations. With distilled knowledge aggregated from all other problems, GPT-5.4-nano narrows the gap and approaches the trajectories and final performance of the larger GPT-5.4-mini.

• Gains are robust to backbone choice: All three tested backbones outperform the best baselines on both TSP and JSSP, with only modest differences in formulation quality and no backbone consistently dominating. Approximate costs reported are GPT-5.4-mini ~$2 (TSP) / ~$3 (JSSP), Claude-Sonnet-4.6 ~$10 / ~$16, and DeepSeek-V4-Flash ~$0.5 / ~$0.8. GPT-5.4-mini is chosen as the default for its performance-cost trade-off.

Methodology in Plain English

FormuEvo starts with a natural-language description of an optimization problem and a template formulation, then asks a "generator" LLM to write several different candidate formulations as executable code (Python with Gurobi). Each candidate is actually run on the solver across a set of Easy instances, and its fitness is the shifted geometric mean of runtimes.

If a candidate crashes or produces wrong objective values relative to known optima, a "repair" LLM gets the error tracebacks and solver logs and tries to fix it; candidates that exceed the repair budget are discarded.

The population then evolves. For crossover, two parent formulations are chosen with probability weighted by their fitness rank. For mutation, a high-performing "elite" is selected. In both cases, a "diagnostic" LLM first inspects the candidates together with their internal solver statistics — presolve results, relaxation strength, branching behavior — and writes a structured diagnosis naming bottlenecks and suggesting directions. The generator LLM then produces the offspring based on that diagnosis, rather than perturbing blindly. The paper describes this as an interpretable "verbal gradient."

After each evaluation, a "reflector" LLM records what changed between parent and offspring and what effect it had, storing it as a memory entry with a condition, a strategy, and an effect. Later diagnoses retrieve relevant entries as extra context, which prunes the search space and avoids repeating failed modifications. Memory-augmented generation is applied with probability 0.7 to avoid overfitting to previously explored regions.

At the end of the search, a "distiller" LLM summarizes the memory library into problem-agnostic knowledge that can be applied zero-shot to entirely new problems or used to help a smaller LLM reason better.

Experimental setup: population size N=8, T=5 generations, 8 offspring per generation, mutation rate 0.3, one repair attempt per failed candidate, fitness measured on 100 Easy instances using SGM runtime with a 1-second shift. Evaluation uses 100 test instances and 5 independent runs with a 600-second per-instance time limit, on Gurobi 10.0 with a single thread and default parameters, on AMD EPYC 9654 processors. ORLM and StepORLM use their own fine-tuned LLMs and are given the same number of generation attempts as FormuEvo; for EvoCut, the paper uses the formulation reported in the original paper where benchmarks overlap (noting EvoCut uses a stronger backbone there), and reruns EvoCut with the same backbone and settings otherwise.

Why This Matters

Impact on research: The paper argues that the field's focus on formulation correctness has left a large gap between what LLMs can generate and what solvers actually need. By recasting formulation design as optimization over a symbolic space and using solver internals as a feedback signal, it offers an alternative to both fine-tuning approaches (which stay close to training data) and local strengthening approaches like EvoCut (which cannot restructure a model). It also demonstrates that distilled modeling knowledge transfers across problems and model scales, a pathway to strong formulation discovery at lower cost.

Real-world applications:

• Manufacturing and production scheduling, where job-shop-type models must be solved repeatedly at scale.
• Transportation and logistics routing, as represented by the traveling salesman benchmark.
• Packing and resource allocation, as represented by the bin packing benchmark.
• Facility location and network planning, as represented by the capacitated facility location benchmark.
• Verification of neural networks, where the paper shows strong gains in a setting with limited human-designed formulation priors.

Industry relevance: Commercial MIP solvers such as Gurobi and COPT are already the workhorses of industrial decision-making. The paper notes that classical "best practice" modeling tricks can now interfere with modern presolving, cut generation, and heuristics, producing counter-intuitive slowdowns. FormuEvo is explicitly designed to adapt to the internals of modern solvers rather than to fixed human intuition, which matters for practitioners whose models must run under time limits on hardware they already own.

Future Directions

• Extending to decomposition algorithms: The stated limitation is that FormuEvo handles static formulations solvable by off-the-shelf general-purpose solvers. Column generation (which iteratively adds variables via a pricing sub-problem) and Benders decomposition (which alternates between a master problem and sub-problems) require dynamic variable and constraint generation, where formulation design and algorithm development are inherently coupled. Jointly evolving reformulations and decomposition-based algorithms is described as promising but substantially more challenging.

• Broadening benchmark coverage: The paper evaluates on five classical problems plus NNV and IMO 2025 Problem 6; extending to more mixed-integer non-linear and real-world problem classes would test whether discovered structural insights generalize further.

• Improving transfer across problem structure: Distilled knowledge is aggregated from all problems except the target. How much shared structure exists between routing, scheduling, packing, location, and assignment problems, and how best to organize distilled knowledge for maximal reuse, remains open.

• Trade-offs across backbone models and cost: The reported differences between backbones are modest but not uniform, so the conditions under which cheaper or more expensive models are preferable — and how best to combine a distiller with a small model — are not fully resolved.

Target Audience

Researchers and practitioners in operations research, mathematical optimization, and automated modeling who care about solver performance rather than only model correctness. It is also relevant to LLM researchers working on evolutionary program search and code generation with execution feedback, and to industrial practitioners in scheduling, routing, packing, location planning, and neural network verification who need models that solve within time limits. Readers without background in MIP formulation and solver internals will find the results tables and formulation details hard to interpret.

Authors’ abstract

Mixed-integer programming (MIP) lies at the core of operations research and industrial optimization. While large language models (LLMs) have recently shown promise in automated MIP modeling from natural language, they prioritize semantic correctness but overlook formulation strength, severely bottlenecking the efficiency of downstream solvers. We propose FormuEvo, an LLM-guided evolutionary framework for automated discovery of solver-efficient MIP formulations. FormuEvo frames MIP formulation design as evolutionary optimization over the symbolic space of MIP formulations, represented as executable modeling programs, by iteratively generating, evaluating, and selecting stronger candidates via LLM-driven crossover, mutation, and repair operations. To move beyond blind exploration, FormuEvo introduces a solver-informed diagnosis mechanism that exploits fine-grained solver statistics as verbal gradients for targeted refinement. Additionally, a structured memory abstracts prior experience into reusable modeling strategies, avoiding redundant exploration while enabling zero-shot transfer to unseen problems and bootstrapping smaller LLMs. Experiments across diverse linear and non-linear problems demonstrate that FormuEvo discovers formulations that significantly outperform both expert-designed formulations and existing LLM-based approaches, accelerating solvers by up to 5.5$\times$, with distilled knowledge transferring effectively across problems and model scales.