Metraipolis › archive › dc_27b60454adcf
SPO: Discovering Adaptive Large Neighborhood Search Operators via Stackelberg Program Optimization — arXiv:2609.31179
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.31179
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T01:38:36.766Z
- SHA-256 of the archived text
05f81aa6df3ab7fd928157d85e717828053cffe9cd07478d456abb82deb39444- Stable URL of this page
https://metraipolis.com/documento/dc_27b60454adcf
How to cite
SPO: Discovering Adaptive Large Neighborhood Search Operators via Stackelberg Program Optimization — arXiv:2609.31179 — arXiv (en), https://arxiv.org/abs/2609.31179 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_27b60454adcf (Metraipolis archive dc_27b60454adcf, sha256 05f81aa6df3ab7fd928157d85e717828053cffe9cd07478d456abb82deb39444)
BibTeX
@misc{dc27b60454adcf,
title = {SPO: Discovering Adaptive Large Neighborhood Search Operators via Stackelberg Program Optimization — arXiv:2609.31179},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.31179},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_27b60454adcf; sha256 05f81aa6df3ab7fd928157d85e717828053cffe9cd07478d456abb82deb39444},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.31179. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-28 in cs.AI). Categorie arXiv: Artificial Intelligence (cs.AI). Pagina del lavoro: https://arxiv.org/abs/2609.31179 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-08T01:12:14.353Z dalla pagina https://arxiv.org/catchup/cs.AI/2026-09-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).