# Planning of Heuristics: Strategic Planning on Large Language Models with Monte Carlo Tree Search for Automating Heuristic Optimization

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 34 references that are in the map.
- First posted on arXiv 17 Feb 2025.

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

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Inner Monologue: Embodied Reasoning through Planning with Language Models](https://mlsanity.com/paper/2207.05608/) (2022)
- [Large Language Models as Optimizers](https://mlsanity.com/paper/2309.03409/) (2023)
- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [LLM+P: Empowering Large Language Models with Optimal Planning Proficiency](https://mlsanity.com/paper/2304.11477/) (2023)
- [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)
- [PromptAgent: Strategic Planning with Language Models Enables Expert-level Prompt Optimization](https://mlsanity.com/paper/2310.16427/) (2023)
- [Learning to Optimize: A Primer and A Benchmark](https://mlsanity.com/paper/2103.12828/) (2021)
- [Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization](https://mlsanity.com/paper/2310.07985/) (2023)
- [Large Language Models to Enhance Bayesian Optimization](https://mlsanity.com/paper/2402.03921/) (2024)
- [Matrix Encoding Networks for Neural Combinatorial Optimization](https://mlsanity.com/paper/2106.11113/) (2021)
- [Improving Multi-turn Emotional Support Dialogue Generation with Lookahead Strategy Planning](https://mlsanity.com/paper/2210.04242/) (2022)
- [LLaMoCo: Instruction Tuning of Large Language Models for Optimization Code Generation](https://mlsanity.com/paper/2403.01131/) (2024)
- [Supporting Self-Reflection at Scale with Large Language Models: Insights from Randomized Field Experiments in Classrooms](https://mlsanity.com/paper/2406.07571/) (2024)
- [Conversational Tree Search: A New Hybrid Dialog Task](https://mlsanity.com/paper/2303.10227/) (2023)

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

- [Large Language Models in Operations Research: Methods, Applications, and Challenges](https://mlsanity.com/paper/2509.18180/) (2025)
- [PathWise: Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs](https://mlsanity.com/paper/2601.20539/) (2026)
- [ACEvo: Adversarial Co-Evolution of Problem Distributions and Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2506.02594/) (2025)
- [A General Highly Accurate Online Planning Method Integrating Large Language Models into Nested Rollout Policy Adaptation for Dialogue Tasks](https://mlsanity.com/paper/2511.21706/) (2025)
- [BEAM: Bi-level Memory-adaptive Algorithmic Evolution for LLM-Powered Heuristic Design](https://mlsanity.com/paper/2604.12898/) (2026)
- [Scientific discovery as meta-optimization: a combinatorial optimization case study](https://mlsanity.com/paper/2606.26728/) (2026)
- [CogMCTS: A Novel Cognitive-Guided Monte Carlo Tree Search Framework for Iterative Heuristic Evolution with Large Language Models](https://mlsanity.com/paper/2512.08609/) (2025)
- [Constraint-aware Path Planning from Natural Language Instructions Using Large Language Models](https://mlsanity.com/paper/2603.19257/) (2026)
- [Budget-Efficient Automatic Algorithm Design via Code Graph](https://mlsanity.com/paper/2605.10598/) (2026)
- [UP-NRPA: User Portrait based Nested Rollout Policy Adaptation for Planning with Large Language Models in Goal-oriented Dialogue Systems](https://mlsanity.com/paper/2606.13683/) (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)
- [Autoresearch in Mixed-Integer Linear and Nonlinear Programming](https://mlsanity.com/paper/2609.39360/) (2026)
- [EPOCH: Coverage-Aware Evolution with Experiential Preference Optimization for LLM-based Automated Heuristic Design](https://mlsanity.com/paper/2610.17379/) (2026)

## Abstract (arXiv)

Heuristics have achieved great success in solving combinatorial optimization problems~(COPs). However, heuristics designed by humans require too much domain knowledge and testing time. Since Large Language Models~(LLMs) possess strong capabilities to understand and generate content with a knowledge base that covers various domains, they offer potential ways to automatically optimize heuristics. To this end, we propose Planning of Heuristics~(PoH), an optimization method that integrates LLM self-reflection with Monte Carlo Tree Search, a well-known planning algorithm. PoH iteratively refines generated heuristics by evaluating their performance and providing improvement suggestions. Our method enables to iteratively evaluate the generated heuristics~(states) and improve them based on the improvement suggestions~(actions) and evaluation results~(rewards), by effectively simulating future states to search for paths with higher rewards. In this paper, we apply PoH to solve the Traveling Salesman Problem and the Flow Shop Scheduling Problem. The experimental results show that PoH outperforms hand-crafted heuristics and other Automatic Heuristic Design methods based on LLMs, and achieves the state-of-the-art performance in automating heuristic optimization with LLMs to solve tested COPs, especially with large sizes.