# SPO: Discovering Adaptive Large Neighborhood Search Operators via Stackelberg Program Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 46 references that are in the map.
- First posted on arXiv 25 Sep 2026.

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

- [LoRA: Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2106.09685/) (2021)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [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)
- [Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/1911.09539/) (2019)
- [PyVRP: a high-performance VRP solver package](https://mlsanity.com/paper/2403.13795/) (2023)
- [Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs](https://mlsanity.com/paper/2107.10201/) (2021)
- [Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning](https://mlsanity.com/paper/2302.01578/) (2023)
- [Learning Large Neighborhood Search Policy for Integer Programming](https://mlsanity.com/paper/2111.03466/) (2021)
- [CALM: Co-evolution of Algorithms and Language Model for Automatic Heuristic Design](https://mlsanity.com/paper/2505.12285/) (2025)
- [Efficient Heuristics Generation for Solving Combinatorial Optimization Problems Using Large Language Models](https://mlsanity.com/paper/2505.12627/) (2025)
- [Neural Deconstruction Search for Vehicle Routing Problems](https://mlsanity.com/paper/2501.03715/) (2025)
- [Dynamic Partial Removal: A Neural Network Heuristic for Large Neighborhood Search](https://mlsanity.com/paper/2005.09330/) (2020)
- [VRPAgent: LLM-Driven Discovery of Heuristic Operators for Vehicle Routing Problems](https://mlsanity.com/paper/2510.07073/) (2025)
- [G-LNS: Generative Large Neighborhood Search for LLM-Based Automatic Heuristic Design](https://mlsanity.com/paper/2602.08253/) (2026)
- [Online Control of Adaptive Large Neighborhood Search using Deep Reinforcement Learning](https://mlsanity.com/paper/2211.00759/) (2022)
- [Balans: Multi-Armed Bandits-based Adaptive Large Neighborhood Search for Mixed-Integer Programming Problem](https://mlsanity.com/paper/2412.14382/) (2024)
- [Large Neighborhood Search based on Neural Construction Heuristics](https://mlsanity.com/paper/2205.00772/) (2022)
- [Large Language Model-Driven Full-Component Evolution of Adaptive Large Neighborhood Search](https://mlsanity.com/paper/2603.06996/) (2026)
- [Game-Theoretic Co-Evolution for LLM-Based Heuristic Discovery](https://mlsanity.com/paper/2601.22896/) (2026)
- [New Adaptive Mechanism for Large Neighborhood Search using Dual Actor-Critic](https://mlsanity.com/paper/2601.11414/) (2026)
- [SpecAHD: Localize to Specialize for Automated Heuristic Design in Large-Scale Routing Problems](https://mlsanity.com/paper/2607.23676/) (2026)

## Abstract (arXiv)

Large neighborhood search (LNS) relies critically on destroy and repair operators, whose effectiveness depends on both adaptation to the evolving LNS state and interaction between the two roles. We introduce Stackelberg Program Optimization (SPO), an LLM-based framework for discovering adaptive executable destroy-repair programs. SPO conditions operator decisions on a compact LNS state, allowing state-dependent behavior to emerge through program discovery, and organizes destroy-repair discovery as a Stackelberg interaction over program space that reflects their asymmetric dependency. Role-specific credits evaluate destroy programs as leaders and repair programs as conditional follower responses, guiding a coupled optimization process that combines LLM generator learning with population-based evolutionary search over programs. Experiments on the traveling salesperson problem and capacitated vehicle routing problem show that SPO outperforms strong baselines across a broad range of settings and generalizes beyond the discovery scale to larger instances and benchmark sets. Behavioral analyses further demonstrate state-dependent operator behavior and coupled destroy-repair improvement during discovery.