# EvoCut: Strengthening Integer Programs via Evolution-Guided Language Models

arXiv: https://arxiv.org/abs/2508.11850 · HTML: https://mlsanity.com/paper/2508.11850/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 54 references that are in the map.
- First posted on arXiv 16 Aug 2025.

## Builds on (most cited first, 17 of 17)

- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model](https://mlsanity.com/paper/2401.02051/) (2024)
- [NL4Opt Competition: Formulating Optimization Problems Based on Their Natural Language Descriptions](https://mlsanity.com/paper/2303.08233/) (2023)
- [ORLM: A Customizable Framework in Training Large Models for Automated Optimization Modeling](https://mlsanity.com/paper/2405.17743/) (2024)
- [Reinforcement Learning for Integer Programming: Learning to Cut](https://mlsanity.com/paper/1906.04859/) (2019)
- [OptiMUS: Scalable Optimization Modeling with (MI)LP Solvers and Large Language Models](https://mlsanity.com/paper/2402.10172/) (2024)
- [LLMOPT: Learning to Define and Solve General Optimization Problems from Scratch](https://mlsanity.com/paper/2410.13213/) (2024)
- [Formal Mathematical Reasoning: A New Frontier in AI](https://mlsanity.com/paper/2412.16075/) (2024)
- [A Systematic Survey on Large Language Models for Algorithm Design](https://mlsanity.com/paper/2410.14716/) (2024)
- [Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning](https://mlsanity.com/paper/2206.13414/) (2022)
- [Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Model](https://mlsanity.com/paper/2302.00244/) (2023)
- [Towards Foundation Models for Mixed Integer Linear Programming](https://mlsanity.com/paper/2410.08288/) (2024)
- [When Large Language Model Meets Optimization](https://mlsanity.com/paper/2405.10098/) (2024)
- [LM4OPT: Unveiling the Potential of Large Language Models in Formulating Mathematical Optimization Problems](https://mlsanity.com/paper/2403.01342/) (2024)
- [Learning to Configure Separators in Branch-and-Cut](https://mlsanity.com/paper/2311.05650/) (2023)
- [Evaluating LLM Reasoning in the Operations Research Domain with ORQA](https://mlsanity.com/paper/2412.17874/) (2024)
- [LLMs for Cold-Start Cutting Plane Separator Configuration](https://mlsanity.com/paper/2412.12038/) (2024)

## Built on by (most cited first, 8 of 8)

- [LLM4Branch: Large Language Model for Discovering Efficient Branching Policies of Integer Programs](https://mlsanity.com/paper/2605.10401/) (2026)
- [Agentic MIP Research: Accelerated Constraint Handler Generation](https://mlsanity.com/paper/2605.09186/) (2026)
- [FLARE: Verifying MILP Reformulations with LLM-Based Theorem Proving](https://mlsanity.com/paper/2608.25220/) (2026)
- [Budget-Efficient Automatic Algorithm Design via Code Graph](https://mlsanity.com/paper/2605.10598/) (2026)
- [FormuEvo: LLM-Guided Evolution for Discovering Solver-Efficient Mixed-Integer Programming Formulations](https://mlsanity.com/paper/2608.23353/) (2026)
- [SOVER: Formal Certification of Optimization Reformulations via LLM-Assisted SMT Verification](https://mlsanity.com/paper/2609.00728/) (2026)
- [Learning to Optimize through Solver-Grounded Self-Play](https://mlsanity.com/paper/2609.34205/) (2026)
- [BiFE: Search-Efficient Discovery of CPU-Only Branching Policies via LLM-based Bi-Fidelity Evolution](https://mlsanity.com/paper/2609.36735/) (2026)

## Abstract (arXiv)

Integer programming (IP) is central to many combinatorial optimization tasks but remains challenging due to its NP-hard nature. A practical way to improve IP solvers is to manually design acceleration cuts, i.e., inequalities that speed up solving. However, this creative process requires deep expertise and has been difficult to automate. Our proposed framework, EvoCut, automates the generation of acceleration cuts at the symbolic modeling level: it reasons over a symbolic MILP model and a natural language description of the problem to discover a reusable set of acceleration cuts that can be used for each concrete instance of the model. EvoCut (i) initializes a population of candidate cuts via an initializer agent that uses an LLM, (ii) empirically screens candidates on a small verification set by checking that reference solutions remain feasible and that at least one stored LP relaxation solution is cut off, and (iii) iteratively refines the population through evolutionary crossover and mutation agents. Compared to baseline MILP formulations solved with a fixed time budget, EvoCut reduces optimality gaps by up to 76% and reaches target gaps up to 7.2 times faster (shifted geometric mean speedup). Ablations show its robustness across different LLM backends and across solvers/cut settings. Code: https://github.com/milad1378yz/EvoCut.