# Efficient Heuristics Generation for Solving Combinatorial Optimization Problems Using Large Language Models

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 May 2025.

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

- [AlphaOPT: Formulating Optimization Programs with Self-Improving LLM Experience Library](https://mlsanity.com/paper/2510.18428/) (2025)
- [Large Language Models in Operations Research: Methods, Applications, and Challenges](https://mlsanity.com/paper/2509.18180/) (2025)
- [Efficient Neural Combinatorial Optimization Solver for the Min-max Heterogeneous Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/2507.21386/) (2025)
- [Refining Hybrid Genetic Search for CVRP via Reinforcement Learning-Finetuned LLM](https://mlsanity.com/paper/2510.11121/) (2025)
- [SeaEvo: Advancing Algorithm Discovery with Strategy Space Evolution](https://mlsanity.com/paper/2604.24372/) (2026)
- [Algorithmic Prompt-Augmentation for Efficient LLM-Based Heuristic Design for A* Search](https://mlsanity.com/paper/2601.19622/) (2026)
- [Contrastive Concept-Tree Search for LLM-Assisted Algorithm Discovery](https://mlsanity.com/paper/2602.03132/) (2026)
- [GRIMIP: A General Framework for Instance-Specific Configuration of MIP Solvers Using LLMs](https://mlsanity.com/paper/2606.23299/) (2026)
- [Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling](https://mlsanity.com/paper/2603.02846/) (2026)
- [CoupleEvo: Evolving Heuristics for Coupled Optimization Problems Using Large Language Models](https://mlsanity.com/paper/2605.06341/) (2026)
- [HMACE: Heterogeneous Multi-Agent Collaborative Evolution for Combinatorial Optimization](https://mlsanity.com/paper/2605.07214/) (2026)
- [Teacher-Aware Evolution of Heuristic Programs from Learned Optimization Policies](https://mlsanity.com/paper/2605.10634/) (2026)
- [Reinforcement Learning without Ground-Truth Solutions can Improve LLMs](https://mlsanity.com/paper/2606.27369/) (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)
- [SPO: Discovering Adaptive Large Neighborhood Search Operators via Stackelberg Program Optimization](https://mlsanity.com/paper/2609.31179/) (2026)
- [AdaEva: Accelerating LLM-Driven Algorithm Design with Adaptive Partial Evaluation](https://mlsanity.com/paper/2610.03896/) (2026)

## Abstract (arXiv)

Recent studies exploited Large Language Models (LLMs) to autonomously generate heuristics for solving Combinatorial Optimization Problems (COPs), by prompting LLMs to first provide search directions and then derive heuristics accordingly. However, the absence of task-specific knowledge in prompts often leads LLMs to provide unspecific search directions, obstructing the derivation of well-performing heuristics. Moreover, evaluating the derived heuristics remains resource-intensive, especially for those semantically equivalent ones, often requiring omissible resource expenditure. To enable LLMs to provide specific search directions, we propose the Hercules algorithm, which leverages our designed Core Abstraction Prompting (CAP) method to abstract the core components from elite heuristics and incorporate them as prior knowledge in prompts. We theoretically prove the effectiveness of CAP in reducing unspecificity and provide empirical results in this work. To reduce computing resources required for evaluating the derived heuristics, we propose few-shot Performance Prediction Prompting (PPP), a first-of-its-kind method for the Heuristic Generation (HG) task. PPP leverages LLMs to predict the fitness values of newly derived heuristics by analyzing their semantic similarity to previously evaluated ones. We further develop two tailored mechanisms for PPP to enhance predictive accuracy and determine unreliable predictions, respectively. The use of PPP makes Hercules more resource-efficient and we name this variant Hercules-P. Extensive experiments across four HG tasks, five COPs, and eight LLMs demonstrate that Hercules outperforms the state-of-the-art LLM-based HG algorithms, while Hercules-P excels at minimizing required computing resources. In addition, we illustrate the effectiveness of CAP, PPP, and the other proposed mechanisms by conducting relevant ablation studies.