# HeurAgenix: Leveraging LLMs for Solving Complex Combinatorial Optimization Challenges

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 63 references that are in the map.
- First posted on arXiv 18 Jun 2025.

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

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Qwen Technical Report](https://mlsanity.com/paper/2309.16609/) (2023)
- [Fine-Tuning Language Models from Human Preferences](https://mlsanity.com/paper/1909.08593/) (2019)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [BranchyNet: Fast Inference via Early Exiting from Deep Neural Networks](https://mlsanity.com/paper/1709.01686/) (2017)
- [Adaptive Computation Time for Recurrent Neural Networks](https://mlsanity.com/paper/1603.08983/) (2016)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [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)
- [Learning with Noisy Labels Revisited: A Study Using Real-World Human Annotations](https://mlsanity.com/paper/2110.12088/) (2021)
- [Spurious Rewards: Rethinking Training Signals in RLVR](https://mlsanity.com/paper/2506.10947/) (2025)
- [Learning Improvement Heuristics for Solving Routing Problems](https://mlsanity.com/paper/1912.05784/) (2019)
- [Monte Carlo Tree Search: A Review of Recent Modifications and Applications](https://mlsanity.com/paper/2103.04931/) (2021)
- [Spatially Adaptive Computation Time for Residual Networks](https://mlsanity.com/paper/1612.02297/) (2016)
- [Process Reward Models That Think](https://mlsanity.com/paper/2504.16828/) (2025)
- [Improving Exploration in Evolution Strategies for Deep Reinforcement Learning via a Population of Novelty-Seeking Agents](https://mlsanity.com/paper/1712.06560/) (2017)
- [Can LLM Graph Reasoning Generalize beyond Pattern Memorization?](https://mlsanity.com/paper/2406.15992/) (2024)
- [Self-Guiding Exploration for Combinatorial Problems](https://mlsanity.com/paper/2405.17950/) (2024)
- [Solving maximum cut problems by simulated annealing](https://mlsanity.com/paper/1505.03068/) (2015)

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

- [AlphaOPT: Formulating Optimization Programs with Self-Improving LLM Experience Library](https://mlsanity.com/paper/2510.18428/) (2025)
- [VRPAgent: LLM-Driven Discovery of Heuristic Operators for Vehicle Routing Problems](https://mlsanity.com/paper/2510.07073/) (2025)
- [Large Language Models in Operations Research: Methods, Applications, and Challenges](https://mlsanity.com/paper/2509.18180/) (2025)
- [What Makes an LLM a Good Optimizer? A Trajectory Analysis of LLM-Guided Evolutionary Search](https://mlsanity.com/paper/2604.19440/) (2026)
- [SeaEvo: Advancing Algorithm Discovery with Strategy Space Evolution](https://mlsanity.com/paper/2604.24372/) (2026)
- [RefineEvo: Planning-Guided Heuristic Evolution with Bidirectional Experience](https://mlsanity.com/paper/2607.11358/) (2026)
- [Contrastive Concept-Tree Search for LLM-Assisted Algorithm Discovery](https://mlsanity.com/paper/2602.03132/) (2026)
- [InvEvolve: Evolving White-Box Inventory Policies via Large Language Models with Performance Guarantees](https://mlsanity.com/paper/2605.00369/) (2026)
- [Agentic MIP Research: Accelerated Constraint Handler Generation](https://mlsanity.com/paper/2605.09186/) (2026)
- [ATLAS: Scaffold-Free Algorithm Synthesis by LLMs via Embedding-Guided Quality-Diversity Search](https://mlsanity.com/paper/2608.15546/) (2026)
- [Deep Reinforcement Learning for Drone Route Optimization in Post-Disaster Road Assessment](https://mlsanity.com/paper/2509.01886/) (2025)
- [A Unified Model for Multi-Task Drone Routing in Post-Disaster Road Assessment](https://mlsanity.com/paper/2510.21525/) (2025)
- [Towards Compositional Generalization in LLMs for Smart Contract Security: A Case Study on Reentrancy Vulnerabilities](https://mlsanity.com/paper/2601.06914/) (2026)
- [Failing to Explore: Language Models on Interactive Tasks](https://mlsanity.com/paper/2601.22345/) (2026)
- [Reinforcement Learning without Ground-Truth Solutions can Improve LLMs](https://mlsanity.com/paper/2606.27369/) (2026)
- [Adaptive Graph-of-Islands Evolution for Automatic Feature Engineering with LLMs](https://mlsanity.com/paper/2607.23286/) (2026)
- [MOSAIC: Adversarial Co-evolution of Specialist Heuristics and Problem Instances for LLM-based Automated Heuristic Design](https://mlsanity.com/paper/2608.07544/) (2026)
- [RouteRepair: Instance-Level Failure Diagnosis and Targeted Repair in LLM-Based Automated Heuristic Design for Routing Optimization](https://mlsanity.com/paper/2609.11452/) (2026)
- [From Hand-Crafted to LLM-Based Variation Operators in Metaheuristics: A Tutorial](https://mlsanity.com/paper/2609.31649/) (2026)
- [HeurEvo: Agentic Evolution of Hybrid Solver-Augmented Heuristics for Time-Critical Mathematical Optimization](https://mlsanity.com/paper/2609.36303/) (2026)
- [From Search to Signal: Online Post-Training in Automatic Heuristic Design](https://mlsanity.com/paper/2609.39383/) (2026)

## Abstract (arXiv)

Heuristic algorithms play a vital role in solving combinatorial optimization (CO) problems, yet traditional designs depend heavily on manual expertise and struggle to generalize across diverse instances. We introduce HeurAgenix, a two-stage hyper-heuristic framework powered by large language models (LLMs) that first evolves heuristics and then selects among them automatically. In the heuristic evolution phase, HeurAgenix leverages an LLM to compare seed heuristic solutions with higher-quality solutions and extract reusable evolution strategies. During problem solving, it dynamically picks the most promising heuristic for each problem state, guided by the LLM's perception ability. For flexibility, this selector can be either a state-of-the-art LLM or a fine-tuned lightweight model with lower inference cost. To mitigate the scarcity of reliable supervision caused by CO complexity, we fine-tune the lightweight heuristic selector with a dual-reward mechanism that jointly exploits singals from selection preferences and state perception, enabling robust selection under noisy annotations. Extensive experiments on canonical benchmarks show that HeurAgenix not only outperforms existing LLM-based hyper-heuristics but also matches or exceeds specialized solvers. Code is available at https://github.com/microsoft/HeurAgenix.