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

Xinyi Ke; Kai Li; Junliang Xing; Yifan Zhang; Jian Cheng

cs.AISep 25, 2026

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

Authors: Xinyi Ke, Kai Li, Junliang Xing, Yifan Zhang, Jian Cheng

Organizations: C2DL, Institute of Automation, Chinese Academy of Sciences · School of Artificial Intelligence, University of Chinese Academy of Sciences · Tsinghua University · University of Chinese Academy of Sciences, Nanjing ·

Abstract

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.

Figures & tables

Figure 1: Overview of Stackelberg Program Optimization (SPO). Program Generation produces leader destroy programs and conditionally generated follower repair programs. LNS Iteration & Evaluation executes each program pair with LNS-state conditioning and evaluates its rollout utility. Coupled Generator–Population Optimization uses role-specific credits to update the LLM generators via GRPO and evolve the executable-program populations. SPO Overview summarizes the hierarchical generation, evaluation, and optimization process.

(a) Traveling Salesperson Problem
Method	Uniform instances (number of nodes $n$ )				TSPLIB (instance-size range)
Method	$50$	$100$	$200$	$500$	$50$ – $100$	$100$ – $200$	$>200$
NN	21.295	23.807	24.884	25.999	26.039	23.143	25.710
FI	6.261	7.711	8.909	10.535	7.336	7.490	11.662
2-opt	3.796	4.197	5.078	5.179	4.120	3.707	5.600
3-opt	2.232	2.905	3.900	4.578	2.859	3.041	4.764

Table 1: Mean final reference gaps (%) on TSP and CVRP benchmarks. Bold indicates the best reported result in each column; lower is better.

Figure 2: Optimization dynamics and behavioral analysis of SPO. (a1) Best-so-far discovery gap across six TSP runs; thick line: mean, shading: across-seed variation. (a2) Anytime best-gap convergence during TSP LNS execution. (b1) State interventions on one discovered TSP pair: Fixed $k$ sets $z_{t}=k$ ; Shuffled permutes the observed state sequence; Inverted maps $z_{t}<10$ to $30$ and otherwise to $0$ . Shown are mean final-gap increases over unmodified execution with 95% bootstrap CIs from 2,000 instance–seed resamples. (b2) Pairwise combinations of destroy and repair programs from the indicated rounds of one CVRP discovery run; colors show mean best gap (power norm $\gamma=0.5$ ). Lower is better; pp = percentage points.

Figure 3: Illustrative case study of state adaptation and destroy–repair interaction. The same TSP instance and incumbent are used throughout. (a1–a2) Destroy and subsequent repair by a discovered pair

(D_{1},R_{1})

under the true state

z_{t}=2

. (b1–b2) The same pair under the counterfactual state

z_{t}=50

. (b3) Starting from the same destruction as in (b1), the paired repair

R_{1}

is replaced by an alternative repair

R_{2}

, yielding a different reconstruction.

Variant	Uniform instances (number of nodes $n$ )				TSPLIB (instance-size range)
Variant	$50$	$100$	$200$	$500$	$50$ – $100$	$100$ – $200$	$>200$
SPO	0.212	0.642	1.274	3.139	0.408	0.574	4.040
w/o Stackelberg Credit	1.398	1.908	3.089	5.995	1.309	2.054	6.647
w/o State Conditioning	0.273	0.816	2.686	6.484	0.592	0.962	6.850

Table 2: Controlled TSP ablations of Stackelberg credit assignment and LNS-state adaptation. Values are mean final reference gaps (%); lower is better.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Prompt form	Parents	Instruction
Mechanism replacement	One	Replace one major decision mechanism while preserving the remainder of the parent design.
State-dependent control redesign	One	Preserve the main mechanism but alter thresholds, budgets, candidate scopes, or adaptation schedules.
Simplification	One	Remove redundant or unnecessarily complex components without introducing a new major mechanism.
Divergent crossover	Two	Use the parents as records of explored ideas and generate a substantially different heuristic.
Shared-principle crossover	Two	Extract a shared high-level principle and implement it through a new program structure.

Appendix

Table 3: Evolutionary prompt forms used during program discovery.

Large Neighborhood Search

Large Neighborhood Search (LNS) improves hard optimization solutions by repeatedly rebuilding selected parts of them.

See all 14 papers

Large Neighborhood Search meets Iterative Neural Constraint Heuristics
Mar 21, 2026Yudong W. Xu, Wenhao Li, Scott Sanner +1Constraint Satisfaction Large Neighborhood Search
Department of Mechanical & Industrial Engineering, University of Toronto · Vector Institute
Large Language Model-Driven Full-Component Evolution of Adaptive Large Neighborhood Search
Mar 7, 2026Shaohua Yu, Tianyu Chen, Linyan Liu +1Automated Heuristic Design Large Neighborhood Search
School of Intelligent Science and Technology, Nanjing University of Science and Technology, Nanjing 210094, China · School of Mechanical Engineering, Nanjing University of Science and Technology, Nanjing 210094, China · Université Paris-Saclay, CentraleSupélec, Laboratoire Génie Industriel, 91190, Gif-sur-Yvette, France +1
AdaEvolve: Adaptive LLM Driven Zeroth-Order Optimization
Feb 23, 2026Mert Cemri, Shubham Agrawal, Akshat Gupta +9Large Language Model-Guided Optimization LLMs for Evolutionary Optimization
University of California, Berkeley · Bespoke Labs

Mar 21, 2026J/K move · Enter open · S save

Large Neighborhood Search meets Iterative Neural Constraint Heuristics

Yudong W. Xu, Wenhao Li, Scott Sanner, Elias B. Khalil

Department of Mechanical & Industrial Engineering, University of Toronto · Vector Institute

Constraint Satisfaction Large Neighborhood Search Automated Heuristic Design

Open paper AskPDF arXiv

Neural networks are being increasingly used as heuristics for constraint satisfaction. These neural methods are often recurrent, learning to iteratively refine candidate assignments. In this work, we make explicit the connection between such iterative neural heuristics and Large Neighborhood Search (LNS), and adapt an existing neural constraint satisfaction method-ConsFormer-into an LNS procedure. We decompose the resulting neural LNS into two standard components: the destroy and repair operators. On the destroy side, we instantiate several classical heuristics and introduce novel prediction-guided operators that exploit the model's internal scores to select neighborhoods. On the repair side, we utilize ConsFormer as a neural repair operator and compare the original sampling-based decoder to a greedy decoder that selects the most likely assignments. Through an empirical study on Sudoku, Graph Coloring, and MaxCut, we find that adapting the neural heuristic to an LNS procedure yields substantial gains over its vanilla settings and improves its competitiveness with classical and neural baselines. We further observe consistent design patterns across tasks: stochastic destroy operators outperform greedy ones, while greedy repair is more effective than sampling-based repair for finding a single high-quality feasible assignment. These findings highlight LNS as a useful lens and design framework for structuring and improving iterative neural approaches.

Abstract

Large Neighborhood Search

Explore similar work

Large Neighborhood Search meets Iterative Neural Constraint Heuristics

Large Language Model-Driven Full-Component Evolution of Adaptive Large Neighborhood Search

AdaEvolve: Adaptive LLM Driven Zeroth-Order Optimization