EvoCut: Strengthening Integer Programs via Evolution-Guided Language Models

2025-08-16 · Milad Yazdani, Mahdi Mostajabdaveh, Samin Aref, Zirui Zhou 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.

📄 PDF Abstract BibTeX arXiv:2508.11850

Code (0)

등록된 구현이 없습니다.

EvoCut: Multi-Layer Evolution-Aware Visual Token Compression for Efficient Large Vision-Language Models

2026-06-01 · Hongyu Lu, Feng Zhang, Wenwei Jin, Huanling Hu 외 arxiv

Large vision-language models (LVLMs) achieve strong performance on image and video understanding tasks, but their inference efficiency is constrained by the large number of visual tokens produced by vision encoders. Most…

An evolutionary solver for linear integer programming

2014-07-27 · João Pedro Pedroso

In this paper we introduce an evolutionary algorithm for the solution of linear integer programs. The strategy is based on the separation of the variables into the integer subset and the continuous subset; the integer va…

Learning Program Synthesis for Integer Sequences from Scratch

2022-02-24 · Thibault Gauthier, Josef Urban

We present a self-learning approach for synthesizing programs from integer sequences. Our method relies on a tree search guided by a learned policy. Our system is tested on the On-Line Encyclopedia of Integer Sequences. …

Program Synthesis Self-Learning

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

2026-08-24 · Haofeng Yuan, Jianing Peng, Jieyi Bi, Ni Zhang 외 arxiv

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 pr…

NICE: Robust Scheduling through Reinforcement Learning-Guided Integer Programming

2021-09-24 · Luke Kenworthy, Siddharth Nayak, Christopher Chin, Hamsa Balakrishnan

Integer programs provide a powerful abstraction for representing a wide range of real-world scheduling problems. Despite their ability to model general scheduling problems, solving large-scale integer programs (IP) remai…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Scheduling