PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Haofeng Yuan, Jianing Peng, Jieyi Bi, Ni Zhang, Shiji Song, Zhiguang Cao

arXiv:2608.23353v1cs.CLcs.NE

TL;DR

MIP modeling needs formulations that are not only correct but also solver-efficient, because equivalent formulations can have very different computational costs. FormuEvo evolves executable formulations using LLM-driven operators, solver-informed diagnosis, and structured memory, and it achieves up to 5.5× solver acceleration while transferring distilled knowledge across problems and model scales.

  • Problem

    Equivalent MIP formulations can differ greatly in solver efficiency, while existing LLM methods prioritize correctness and executability over formulation strength.

  • Method

    FormuEvo performs evolutionary search over executable MIP formulations using LLM-driven crossover, mutation, repair, solver-informed diagnosis, and structured memory.

  • Results

    FormuEvo significantly outperforms state-of-the-art baselines and accelerates modern MIP solvers by up to 5.5×.

  • Takeaways & Limitations

    Distilled FormuEvo knowledge transfers to unseen problems and smaller LLMs, supporting generalizability across problems and model scales.

  • Takeaways & Limitations

    FormuEvo focuses on static formulations and does not yet jointly evolve dynamic relaxation or decomposition-based solution algorithms.

Abstract

from arXiv · show

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.

1 Introduction

MIP formulations can be mathematically equivalent yet differ dramatically in solver efficiency, while existing LLM methods emphasize correctness and executability. FormuEvo addresses this gap by evolving executable formulations with solver-informed diagnosis and structured memory, achieving solver acceleration of up to 5.5×.

  • Motivation: Equivalent MIP formulations can differ by orders of magnitude in computational efficiency despite guaranteeing the same optimal solution.Solver efficiency depends on formulation structure, not only semantic correctness.
  • Motivation: Discovering solver-efficient formulations is expertise-intensive because modern solver behavior can make classical modeling practices counterproductive.Strengthening constraints and symmetry-breaking rules may interfere with presolving, cut generation, and heuristics.
  • Motivation: Existing LLMs generate executable, correct MIP models but often produce computationally naive formulations that are weak for large-scale optimization.Their objective is correctness and executability rather than formulation strength.
  • Approach: FormuEvo reframes formulation design as evolutionary optimization over executable MIP programs, applying LLM-driven crossover, mutation, and repair guided by solver performance.The framework maintains and progressively improves candidate formulations rather than relying on single-pass generation.
  • Approach: Solver-informed diagnosis converts fine-grained solver statistics into verbal gradients for targeted refinement, while structured memory stores reusable modeling strategies.These mechanisms reduce blind exploration and support transfer to unseen problems and smaller LLMs.
  • Results: 5.5× solver acceleration is achieved as FormuEvo discovers formulations that outperform state-of-the-art baselines.The reported result includes comparisons against expert-designed and other baseline formulations.

2 Related Work

Prior work establishes formulation design as difficult and shows that LLM-based MIP modeling improves domain fidelity while remaining instance-level, open-loop, and focused on correctness over strength. LLM-guided evolutionary search offers a relevant paradigm, but its adaptation to MIP formulation remains limited.

  • MIP Modeling and Formulation: Classical MIP techniques include valid inequalities, cutting planes, symmetry-breaking constraints, extended variables, and reformulations.These techniques can sometimes conflict with modern solver internals and degrade performance.
  • LLM for Automated MIP Modeling: Recent LLM methods automate MIP modeling through structured formulations, agent systems, and fine-tuning, improving domain fidelity.The related approaches generate formulations from natural-language problem descriptions.
  • LLM for Automated MIP Modeling: Existing LLM approaches generate instance-tied formulations and prioritize mathematical correctness, producing structurally weak models for large-scale optimization.They do not generally discover generalized, instance-agnostic formulations at the problem level.
  • LLM-Guided Evolutionary Search: LLM-guided evolutionary search has advanced automated algorithm and heuristic design, but little work has adapted it to MIP formulation.The related paradigm uses LLMs as evolutionary operators over executable code.

3 FormuEvo

FormuEvo treats solver-efficient MIP formulation discovery as evolutionary optimization over executable programs. Its search combines solver evaluation, repair, diagnosis, evolutionary operators, and structured memory to improve candidates and reuse experience.

  • 3.1 Problem Formalization: A MIP formulation is represented as an executable program encoding continuous and integer variables, an objective, and equality and inequality constraints.The symbolic space F contains semantically correct and syntactically valid programs for a problem.
  • 3.1 Problem Formalization: Formulations in F may have different structures while remaining optimization-equivalent and producing the same optimal solution.Their solver runtimes can nevertheless differ substantially because of relaxation, symmetry, and implementation effects.
  • 3.1 Problem Formalization: FormuEvo minimizes downstream solver cost over the discrete formulation space, using LLMs as evolutionary operators because the objective is expensive and non-differentiable.The cost function ϕ(f) can be measured by runtime with a downstream MIP solver.
  • 3.2 LLM-Guided Evolutionary Search: The evolutionary loop maintains candidate populations and coordinates generator, diagnostic, repair, reflector, and distiller LLM modules.Initialization prompts the generator to produce diverse variants, including alternative variables, equivalent constraints, and implementation changes.
  • 3.2 LLM-Guided Evolutionary Search: Candidates are executed on solver instances, repaired when compilation or correctness checks fail, and scored using shifted geometric mean runtime.Candidates exceeding the repair budget are discarded, while evaluated experience is stored for later retrieval.
  • 3.2 LLM-Guided Evolutionary Search: Each generation preserves top-performing formulations and creates offspring through fitness-guided crossover and elite mutation before repeating evaluation and repair.The best formulation across generations is returned as the final formulation.
  • 3.3 Solver-Informed Diagnosis: Solver-informed diagnosis supplements scalar runtime with presolving, relaxation, and branching statistics that expose structural bottlenecks.The diagnostic LLM converts these signals into targeted directions before crossover or mutation.
  • 3.4 Structured Memory: Structured memory records problem conditions, modeling strategies, and observed solver effects to reduce redundant exploration and support retrieval.A distiller LLM later removes instance-specific details to produce problem-agnostic knowledge for transfer across problems and model scales.

4 Experiments

FormuEvo is evaluated across diverse classical and novel MIP benchmarks against expert-designed and LLM-based baselines. It generally improves solver performance, while ablations, transfer experiments, and backbone comparisons examine the framework’s mechanisms and robustness.

  • Benchmarks: FormuEvo is tested on classical MILP/MINLP benchmarks spanning routing, scheduling, packing, location, and assignment, plus two less-explored optimization problems.Easy instances support evolution, while larger or separate Hard instances evaluate final performance.
  • Baselines and setup: The evaluation compares FormuEvo with standard and state-of-the-art expert-designed formulations and LLM-based baselines under matched generation settings where applicable.Experiments use Gurobi 10.0, single-threaded execution, and fixed experimental settings described for the compared systems.
  • Main results: FormuEvo accelerates solvers by up to 5.5× over the best baselines and achieves the best runtime on most instances across nearly all benchmarks.The reported metrics are runtime, best-runtime wins, and instances solved to optimality within the time limit.
  • Main results: On TSP Hard instances, MCF-RLT solves 0/100 instances despite its theoretically tight relaxation, whereas solver-informed FormuEvo targets practical computational efficiency.The result illustrates that theoretical relaxation tightness and downstream solver efficiency can diverge.
  • Main results: LLM baselines often produce correct but weak textbook formulations, and fail on some novel problems, exposing a gap between formulation correctness and efficiency.ORLM failed to produce a correct QAP formulation, while both ORLM and StepORLM failed on the novel NNV and IMO problems.
  • Ablation, transfer, and robustness: Ablations show that removing either solver-informed diagnosis or memory degrades performance, while distilled knowledge improves smaller-model transfer and backbone gains remain broadly robust.GPT-5.4-nano approaches GPT-5.4-mini performance with distilled knowledge; different backbones consistently outperform the best baselines with modest quality differences.

5 Conclusions

FormuEvo automatically discovers solver-efficient static MIP formulations through solver-informed evolutionary search and structured memory. It outperforms state-of-the-art baselines and transfers distilled knowledge across problems and model scales.

  • FormuEvo combines evolutionary formulation discovery with solver-informed diagnosis and structured memory for directed, systematic improvement.
  • Up to 5.5× acceleration over state-of-the-art baselines demonstrates significant solver-efficiency gains.
  • Distilled knowledge transfers FormuEvo to unseen problems and smaller LLMs.
  • Extending the framework beyond static formulations to jointly evolve reformulations and decomposition algorithms remains future work.

A Problems and Formulations

The appendix describes benchmark problems, standard and evolved formulations, and representative structural choices across routing, scheduling, packing, and assignment models.

  • A Problems and Formulations: The appendix documents benchmark descriptions, standard formulations, baselines, and FormuEvo-discovered formulations, with instance splits summarized in Table 5.
  • A.1 Traveling Salesman Problem (TSP): TSP seeks a minimum-cost Hamiltonian cycle visiting every city exactly once while excluding disconnected subtours.
  • Standard MIP formulation: TSP formulations use binary arc variables and auxiliary ordering or flow variables for subtour elimination, with FormuEvo adding selective lifted DFJ cuts to SCF connectivity.
  • Standard MIP formulation: JSSP models assign operations to machines and sequence them using start times, makespan, processing times, and disjunctive variables.
  • FormuEvo formulation: FormuEvo strengthens JSSP disjunctive models with tight bounds, tail-based makespan constraints, symmetry breaking, and bound-driven binary fixing.
  • A.3 Bin Packing Problem (BPP) Problem description: BPP assigns weighted items to capacity-limited identical bins, with baselines spanning assignment, flow-network, compressed-network, and symmetry-breaking formulations.
  • FormuEvo formulation: FormuEvo’s BPP formulation uses GCD-scaled weights, pre-packs capacity-filling items, and compresses the flow network to subset-sum-reachable loads.
  • A.4 Capacitated Facility Location Problem (CFLP): CFLP selects facilities and shipment quantities to satisfy customer demand under facility opening costs and capacity constraints.

B Implementation Details of FormuEvo

FormuEvo initializes and evolves executable Gurobi formulations through LLM-generated populations, diagnosis-guided crossover and mutation, evaluation, selection, repair, and memory reflection.

  • Generator LLM for Initialization: Initialization repeatedly generates candidate populations, evaluates and repairs formulations, and updates the best formulation.
  • 43: // Knowledge distillation for transfer: The generator is instructed to preserve mathematical correctness while producing efficient, numerically stable Python gurobipy models using available memory.
  • B Implementation Details of FormuEvo: FormuEvo takes a problem description, formulation template, population size, generations, mutation rate, memory rate, and optional external knowledge base.
  • Crossover and Mutation: Crossover samples two parents, diagnoses their solver statistics with or without memory, and generates offspring combining complementary strengths or orthogonal directions.
  • Crossover and Mutation: Mutation selects elite formulations and applies general, exploratory, searching, or polyhedral operators at configured rates.
  • Diagnostic LLM: Diagnostic reports identify primary and secondary bottlenecks from solver profiles, rank mutation recommendations, and specify properties to preserve and trade-offs.
  • Memory Reflection: Each evaluated formulation receives fitness based on runtime-oriented solver performance, while reflection distills parent-offspring changes into reusable experience triplets.

C.1 Statistical Significance Analysis

FormuEvo achieves statistically significant runtime improvements across most evaluated problems, with stronger evidence on harder instances. Improvements are less significant for easy BPP and QAP instances, where solver runtimes are already extremely short.

  • For most problems, FormuEvo significantly improves per-instance runtimes over the best baselines, with p < 0.01 across difficulty categories.The reported problems include TSP, CFLP, NNV, and IMO.
  • Statistical significance generally increases with instance difficulty, indicating larger advantages on challenging instances.The passage links this pattern to formulation strength affecting relaxation quality and branching behavior.
  • BPP and QAP show less significant improvements on Easy instances.The authors attribute this to a floor effect caused by very short runtimes and greater sensitivity to runtime variance.
  • As instance scale and complexity grow, FormuEvo's advantages become increasingly significant.The reported pattern supports scalability on Medium and Hard instances.

C.2 Robustness Across Different Solvers

FormuEvo remains effective when evaluated with COPT and SCIP, but the relative quality of formulations varies across solver backends. This indicates that formulation performance depends partly on the downstream solver.

  • FormuEvo-G denotes Gurobi-evolved formulations adapted directly to COPT and SCIP, whereas FormuEvo denotes formulations evolved under the corresponding solver.This distinction separates direct solver-specific evolution from cross-solver adaptation.
  • FormuEvo consistently achieves significant improvements across COPT and SCIP, showing that the framework is not restricted to one optimization backend.The evaluation replaces Gurobi and reruns evolution under both alternative solvers.
  • Relative performance varies substantially across solvers, including differences between FormuEvo and FormuEvo-G.The results suggest that the most effective formulation for one solver may not transfer unchanged to another.
  • For most TSP Hard instances, SCIP fails to solve to optimality within the time limit, making Wins less indicative.This caveat limits interpretation of the Wins metric for that setting.

C.3 Generalization to Public Benchmarks

FormuEvo generalizes from small evolution instances to substantially larger and differently distributed public TSP and JSSP benchmarks. Primal-dual gap curves are used because these instances are generally not solved to optimality within practical time limits.

  • FormuEvo is evaluated on 200-city Solomon TSP instances and 100 × 20 Taillard JSSP instances.These benchmarks are more challenging than the Hard instances used during evolution.
  • Figure 5 compares performance on the Solomon TSP benchmark and the Taillard JSSP benchmark.The left panel covers TSP and the right panel covers JSSP.
  • Because optimal solutions are generally impractical to obtain, performance is reported using primal-dual gap curves over solving time.Smaller gaps indicate better optimization performance.
  • FormuEvo formulations generalize effectively to larger-scale benchmarks with different distributions despite being evolved only on small instances.The result supports transfer beyond the scale and distribution of the evolution data.
  • Tighter FormuEvo formulations enable solvers to identify high-quality feasible solutions more quickly on these large-scale instances.

C.4 Analysis of Evolutionary Search Hyperparameters

Evolutionary search performs best under a balanced mutation and memory configuration. Excessive memory reuse can reduce search diversity, so occasional memory-free generation is beneficial.

  • FormuEvo achieves its best overall performance on TSP with mutation rate ρ = 0.3 and memory usage rate γ = 0.7.These values are selected as the default setting.
  • A memory usage rate of γ = 1.0 does not always improve performance.The result suggests that maximum memory reuse is not uniformly beneficial.
  • Occasional memory-free generation helps maintain search diversity and prevents excessive reliance on previously explored patterns.

C.5 Discussion with Existing LLM-based Modeling Approaches

FormuEvo differs from existing LLM-based modeling approaches by treating formulation design as solver-guided evolutionary optimization rather than static generation. It reduces training and reuse costs while supporting transfer across instances and modeling settings.

  • Optimization capability and continual improvement: FormuEvo frames formulation design as explicit optimization over symbolic MIP formulations, using iterative solver-feedback-guided evolution.The framework contrasts evolutionary search with static formulation generation by pretrained models.
  • Optimization capability and continual improvement: FormuEvo can discover high-quality formulations that outperform expert-designed formulations and recent LLM-based approaches, even with a small evolutionary budget.The comparison is reported in the discussion of results and Figure 6.
  • Offline and online computational costs: FormuEvo requires no task-specific fine-tuning and can run through lightweight API-based interaction with general-purpose LLMs in CPU-only environments.The evolutionary process typically takes one to several hours, depending on problem complexity and evaluation-instance count.
  • Offline and online computational costs: A strong formulation evolved for a problem family can be reused on unseen instances with essentially no additional optimization cost.This reuse is especially relevant when many instances share underlying optimization structures.
  • Generality and transferability: Unlike fine-tuned approaches sensitive to prompt and interface shifts, FormuEvo operates with general-purpose foundation LLMs and symbolic formulations.The supplied passage introduces this contrast but truncates the subsequent transferability discussion.
  • Methodological role of LLMs: FormuEvo uses LLMs as methodological components for evolutionary search, while the authors conceived, prepared, and finalized the core ideas and manuscript.LLMs also assisted with code writing and text polishing.
Loading 2608.23353v1…