![[2508.11850] EvoCut: Strengthening Integer Programs via Evolution-Guided Language Models](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2508.11850] EvoCut: Strengthening Integer Programs via Evolution-Guided Language Models
Summary
EvoCut automates the generation of acceleration cuts for integer programming, significantly improving solver performance by leveraging evolution-guided language models.
Why It Matters
This research addresses the challenges of integer programming, a critical area in combinatorial optimization. By automating the generation of acceleration cuts, EvoCut enhances solver efficiency, potentially impacting various applications in operations research and AI-driven optimization tasks.
Key Takeaways
- EvoCut automates the generation of acceleration cuts for integer programming.
- It utilizes evolution-guided language models to improve solver performance.
- The framework reduces optimality gaps by up to 76% and speeds up solutions significantly.
- EvoCut demonstrates robustness across different LLM backends and solver settings.
- This advancement could streamline complex optimization tasks in various industries.
Computer Science > Artificial Intelligence arXiv:2508.11850 (cs) [Submitted on 16 Aug 2025 (v1), last revised 12 Feb 2026 (this version, v2)] Title:EvoCut: Strengthening Integer Programs via Evolution-Guided Language Models Authors:Milad Yazdani, Mahdi Mostajabdaveh, Samin Aref, Zirui Zhou View a PDF of the paper titled EvoCut: Strengthening Integer Programs via Evolution-Guided Language Models, by Milad Yazdani and 3 other authors View PDF HTML (experimental) Abstract: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. Comp...
