SPO is an LLM-based framework that discovers adaptive destroy and repair operators for large neighborhood search (LNS). It conditions operator decisions on a compact LNS state and organizes discovery as a Stackelberg game where destroy acts as leader and repair as follower, generating role-specific credits to guide optimization. Experiments on the traveling salesperson problem (TSP) and capacitated vehicle routing problem (CVRP) show that SPO discovers high-quality operators that outperform strong baselines and generalize to larger instances and benchmark sets. Behavioral analyses confirm state-dependent operator behavior and coupled destroy-repair improvement during discovery. The work is interesting because it automates the design of adaptive and interacting LNS operators using LLMs and a game-theoretic framework, addressing a key challenge in combinatorial optimization.
LLM-discovered search operators adapt destruction and repair to search state
SPO jointly discovers executable operators for large neighborhood search using a leader-follower optimization framework and state-dependent program behavior.
CDL, 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 · AiRiA
In one line
SPO discovers adaptive destroy-repair programs for LNS using Stackelberg optimization and outperforms baselines on TSP and CVRP.
Before you read this
Two ideas this paper builds onThe authors represent large neighborhood search operators as executable programs that receive a compact description of the current search state.
How it works
before and afterThe Daily Edition
The front page in your inbox each weekday morning: the lead, the picks, and why each one earned its place.