Large Neighborhood Search (LNS) relies on destroy and repair operators, whose performance hinges on adaptation to the evolving LNS state and their mutual interaction. We introduce Stackelberg Program Optimization (SPO), an LLM‑driven framework that automatically discovers executable adaptive destroy‑repair programs. SPO conditions operator decisions on a compact LNS state, allowing state‑dependent behavior to emerge during program discovery, and models destroy‑repair discovery as a Stackelberg interaction in program space, reflecting their asymmetric dependency. Role‑specific credits treat destroy programs as leaders and repair programs as conditional followers, guiding a coupled optimization 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 diverse settings and generalizes to larger instances and benchmark suites. Behavioral analyses further reveal clear state‑dependent operator behavior and coupled improvement of destroy and repair during discovery.
Review