← Back to all news
arXiv AI

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

The paper introduces Stackelberg Program Optimization (SPO), a framework that uses large language models to discover adaptive destroy‑repair operators for large neighborhood search. SPO conditions operator decisions on a compact state representation, enabling state‑dependent behavior, and frames the discovery process as a Stackelberg game where destroy operators act as leaders and repair operators as conditional followers. Experiments on the traveling salesperson and capacitated vehicle routing problems show that SPO outperforms strong baselines, generalizes to larger instances, and exhibits coupled improvement in operator behavior during discovery.

Related stories

arXiv AI
Sep 12

RouteRepair: Instance-Level Failure Diagnosis and Targeted Repair in LLM-Based Automated Heuristic Design for Routing Optimization

RouteRepair is a method that diagnoses specific weaknesses in large language model (LLM)-generated routing heuristics by evaluating performance at the instance level and then applies targeted modifications to the heuristic components that are failing, while preserving components that already perform well. It combines routing evidence, solver behavior, and program context to set bounded repair objectives and validates each change through matched parent-child evaluation of failure recovery and collateral degradation. Experiments on the traveling salesman problem (TSP) and capacitated vehicle routing problem (CVRP) show significant reductions in optimality gaps and route costs, demonstrating that failure-aware, evidence-constrained refinement can improve routing heuristics on difficult instances while maintaining performance on easier cases.

By Binghao Ji, Di Huang, Jiahui Fang, Zhiyuan Liu
llms
More like this →
arXiv Machine Learning
Aug 5

Beyond Solving: Prescriptive Probing for Neural Routing Solvers

arXiv:2602. 07216v2 Announce Type: replace Abstract: Neural combinatorial optimization (NCO) trains fast heuristics for routing problems, but planners often need more than a single solve: they ask which stop to drop, which transition to preserve, or which subset of stops to remove if a route is infeasible.

By Reuben Narad, L\'eonard Boussioux, Michael Wagner
reinforcement-learningbenchmarkssafety
More like this →
arXiv Machine Learning
Sep 3

RideSkill: A Hierarchical Algorithm for Generalized Ride Sharing with LLM-Driven Automatic Evolution

RideSkill is a hierarchical algorithm for generalized ride sharing that uses large language models (LLMs) to automatically design and train a skill repository, a combiner, and a repositioner. The combiner assigns vehicle-specific skills for adaptive dispatch across varying scenarios and objectives, while the repositioner moves idle vehicles to emerging regions to avoid conflicts. By training all components via an LLM-based evolutionary method, RideSkill eliminates the need for real-time LLM calls, enabling high-performance deployment in large-scale systems.

By Zijian Zhao, Sen Li, Xialiang Tong, Mingxuan Yuan
llmsagentsreinforcement-learning
More like this →
arXiv AI
Jun 2

LLM-Driven Co-Evolutionary Automated Heuristic Design for Bi-Component Coupled Combinatorial Optimization

arXiv:2606. 00718v1 Announce Type: new Abstract: While Large Language Models (LLMs) have recently shown promise in Automated Heuristic Design (AHD), existing methods typically generate and evolve heuristics as a single operator or search strategy, limiting their ability to model strong coupling among multiple decision substructures in problems such as the Traveling Thief Problem (TTP) and the Traveling Purchaser Problem (TPP).

By Mingen Kuang, Xudong Deng, Xi Lin, Ye Fan, Jianyong Sun, Jialong Shi
llms
More like this →