HeurEvo: Agentic Evolution of Hybrid Solver-Augmented Heuristics for Time-Critical Mathematical Optimization
Feijie Wu, Hugo Barbalho, Konstantina Mellou and colleagues at Microsoft Research and Purdue introduce HeurEvo, which co-evolves the plan, code and reusable components of hybrid heuristics that call mathematical-programming solvers under tight runtime limits.
Ask this paper
Three evolving layers. A planner chooses which components to use, how to combine them and how to split runtime across stages; a coder implements the plan; a component evolver updates a shared component pool. An interpreter agent reads execution results and suggests improvements, inside an island-based evolutionary loop.
Synthetic tasks. With a two-minute runtime budget, HeurEvo's mean gap is -2.22% on training instances and -1.45% on held-out instances relative to Gurobi's 48-hour incumbents, meaning it finds better solutions than Gurobi given 48 hours.
Breadth. It is evaluated on 11 synthetic tasks, six MIPLIB-NL-derived problems and four AlphaEvolve geometry families, against OpenEvolve, AdaEvolve, EvoX and heuristic-design baselines, and improves the best reported results on several geometry problems including hexagon packing.
Abstract
Recent advances in agentic heuristic design use AI agents and execution feedback to automate algorithm discovery for challenging optimization problems. In many practical settings, high-quality solutions must be obtained under strict runtime constraints, motivating hybrid approaches that combine problem-specific heuristics with powerful mathematical programming solvers. However, existing approaches typically improve heuristic components within predefined procedures or tune solver configurations in isolation. This limits holistic adaptation of where to allocate computation, how to leverage solvers, and how to refine the overall algorithmic structure. To address these limitations, we propose HeurEvo, an automated plan--code--component co-evolution framework that jointly evolves the high-level algorithmic structures, their implementations, and a shared pool of reusable components. A planner determines which algorithmic components to use, how to combine them, and how to allocate runtime across stages, a coder realizes the resulting plan as executable code, while a component evolver updates the shared component pool. Within an island-based evolutionary framework, plans and implementations co-evolve with feedback from an interpreter agent that analyzes execution results and identifies opportunities for improvement. Across diverse combinatorial optimization benchmarks and challenging MIPLIB instances, HeurEvo finds high-quality solutions within tight runtime budgets, often matching or surpassing state-of-the-art optimization solvers given hours or days of computation. On several nonlinear geometry problems such as hexagon packing, it also improves upon the best previously reported results. These results highlight the value of jointly searching over algorithmic structure and implementation for agentic heuristic design.