FormuEvo: LLM-Guided Evolution for Discovering Solver-Efficient Mixed-Integer Programming Formulations
FormuEvo employs LLM-guided evolutionary algorithms to optimize MIP formulations, achieving up to 5.5× speedup over baselines.
Key Findings
Methodology
This paper introduces FormuEvo, an evolutionary framework that models MIP formulation design as a symbolic search space optimization. It leverages large language models (LLMs) to generate, diagnose, and repair candidate formulations through crossover and mutation, guided by solver performance metrics. The approach incorporates a solver-informed diagnosis mechanism that interprets fine-grained solver statistics into verbal gradients, directing structural improvements. Additionally, a structured memory component abstracts prior experience into reusable strategies, enabling zero-shot transfer and model distillation. Extensive experiments across linear and nonlinear benchmarks demonstrate that FormuEvo discovers formulations that significantly outperform both expert-crafted and existing LLM-generated formulations, with speedups up to 5.5×, highlighting its effectiveness and generalization capabilities.
Key Results
- On diverse benchmarks including TSP, JSSP, BPP, CFLP, and QAP, FormuEvo outperformed traditional and LLM baselines, with an average runtime reduction of 4.2× and a maximum of 5.5×. It consistently achieved the best solution times across most instances, especially on complex problems.
- The solver-informed diagnosis mechanism effectively identifies structural bottlenecks, guiding targeted formula refinements that lead to tighter relaxations and fewer branch-and-bound nodes. Knowledge distillation enabled robust transfer across different problem types and model sizes.
- FormuEvo produced more compact, robust formulas that reduced search space and improved solver stability. The approach demonstrated strong generalization, solving unseen problem instances efficiently and outperforming state-of-the-art methods.
Significance
This work advances automated MIP modeling by integrating deep learning, evolutionary algorithms, and solver feedback, addressing the long-standing challenge of designing solver-efficient formulations. It reduces reliance on expert intuition, accelerates problem-solving in industrial applications, and opens pathways for fully automated optimization pipelines. The solver-informed diagnosis and knowledge transfer mechanisms set new standards for generalizable, high-performance optimization modeling, promising broad impact in operations research and industrial engineering.
Technical Contribution
The paper proposes a novel LLM-guided evolutionary framework that models the entire formulation space as a structured symbolic domain. It introduces a solver-informed diagnosis module that interprets solver internal statistics into actionable guidance, enabling targeted structural improvements. The structured memory component captures and reuses successful strategies, facilitating knowledge transfer and model compression via distillation. These innovations collectively enable systematic, goal-oriented optimization of MIP formulations, surpassing existing heuristic and learning-based approaches in both efficiency and robustness.
Novelty
This is the first work to apply LLM-guided evolutionary search over the entire symbolic space of MIP formulations, directly incorporating solver internal statistics for targeted refinement. Unlike prior methods focusing solely on correctness or instance-specific modeling, it emphasizes structural optimization for solver efficiency. The integration of structured memory and knowledge distillation for cross-problem transfer further distinguishes this approach from existing literature.
Limitations
- The method relies heavily on detailed solver statistics, which can be computationally expensive to gather, especially for large-scale problems, limiting real-time applicability.
- Its effectiveness on highly nonlinear or constraint-rich problems remains to be validated, as current experiments focus mainly on linear and moderately nonlinear benchmarks.
- The evolutionary process, though effective, is time-consuming and may require significant computational resources, hindering scalability in some industrial contexts.
Future Work
Future directions include developing more efficient diagnostic tools to reduce computational overhead, extending the framework to handle highly nonlinear and complex constraints, and integrating reinforcement learning to further automate and accelerate the search process. Enhancing transferability across broader problem domains and improving interpretability of the formulas are also promising avenues.
AI Executive Summary
Mixed-integer programming (MIP) is a cornerstone of decision-making in industries such as manufacturing, logistics, and finance. However, the efficiency of solving these problems heavily depends on the formulation quality. Traditional formula design relies on expert intuition and classical techniques like valid inequalities and symmetry-breaking rules, which often become outdated with advances in solver internals. Recent progress in large language models (LLMs) has enabled automated modeling from natural language, but these models primarily focus on correctness rather than solver efficiency. Consequently, many generated formulations, while valid, are suboptimal in computational performance.
To address this challenge, the authors propose FormuEvo, an innovative framework that combines LLMs with evolutionary algorithms to discover solver-efficient MIP formulations. The core idea is to treat formulation design as a symbolic search problem, where candidate formulas evolve through crossover and mutation operations driven by LLMs. These operations are guided by solver performance metrics, which are interpreted via a solver-informed diagnosis mechanism that converts internal solver statistics into verbal guidance for structural improvements. Additionally, a structured memory component captures and reuses successful strategies, enabling knowledge transfer across problems and models.
The methodology involves initializing a population of candidate formulas using LLMs, evaluating their performance on representative instances with Gurobi, diagnosing bottlenecks, and iteratively refining formulas through genetic operations. The process continues over multiple generations, with the best-performing formulas selected for final deployment. Experimental results across benchmarks like TSP, JSSP, BPP, CFLP, and QAP demonstrate that FormuEvo outperforms both classical expert-designed formulations and recent LLM-based approaches, achieving up to 5.5× acceleration. The approach not only improves runtime but also produces more compact, structurally robust formulas, with strong transferability to unseen problems.
This work significantly advances automated optimization modeling, offering a scalable, generalizable, and high-performance solution. Its integration of deep learning, symbolic evolution, and solver feedback paves the way for fully automated, intelligent decision-making systems. Future research will focus on reducing computational costs, extending to nonlinear problems, and enhancing interpretability and transferability, aiming to revolutionize industrial optimization workflows.
Deep Dive
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.