CS Paper Radar

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

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

cs.AI ·submitted 2026-09-25 12:12 UTC · v1
benchmark

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.AI ·2026-09-10 ·Binghao Ji, Di Huang, Jiahui Fang, Zhiyuan Liu
similarity 0.60
Abstract · 22 pages, 13 figures, 11 tables

Efficient routing optimization is essential to freight transportation, urban logistics, and shared mobility, where high-quality heuristics are often required under limited computational budgets. Recent large language model (LLM)-based automated heuristic design methods can generate effective routing rules, but aggregate evaluation may mask recurrent failures on particular instance structures. To address this limitation, this study develops RouteRepair, which diagnoses parent-specific weaknesses from instance-level performance and applies targeted modifications to the corresponding heuristic components while protecting behavior that already performs well. Routing evidence, solver behavior, and program context are combined to define bounded repair objectives, and each intervention is validated through matched parent-child evaluation of failure recovery and collateral degradation. Experiments on the traveling salesman problem (TSP) and capacitated vehicle routing problem (CVRP) span constructive search, guided local search, and ant colony optimization. RouteRepair-GLS reduces the mean TSP optimality gap from 1.7476% to 0.7587%, while the constructive CVRP heuristic lowers average route cost by 1.91% relative to the savings heuristic; the generated ACO priors also outperform matched hand-designed priors. These results show that failure-aware, evidence-constrained refinement can improve routing heuristics on difficult instances while preserving performance on cases they already solve well.

0.24

Genetic Programming with Behaviour-based Niching for Learning Guided Local Search in Vehicle Routing Problems

cs.NE ·2026-09-21 ·Saining Liu, Yi Mei, Mengjie Zhang
similarity 0.58
Abstract · 15 pages, 3 figures

Genetic Programming Guided Local Search (GPGLS) learns utility functions that guide local search for vehicle routing. Its evolving programs can have similar fitness while inducing different search behaviour, making fitness alone an incomplete basis for population diversity management. We propose GPGLS with Behaviour-based Niching (BN-GPGLS), which characterises programs through six operator-level descriptors collected during local search. A current-generation archive selects fitness-competitive, compact representatives from strata of a behaviour score. Fixed policies use archive parents continuously, whereas adaptive policies activate them using training-fitness and standardised behaviour-dispersion signals, optionally with a tree-size condition. We compare four behaviour-based variants with a no-archive GPGLS control and fitness-based niching over 30 seed-matched runs on generated 200-customer instances. BN-Adaptive achieves the best descriptive average rank on a separate 90-instance monitoring set; aggregate routing-cost differences are small. All five archive policies produce lower final-population median tree sizes than the GPGLS control, with paired Wilcoxon comparisons remaining significant after Holm adjustment. These results identify useful solution-quality and program-size trade-offs within the evaluated setting, without attributing the size reductions to behaviour representation alone.

0.41

Dream-COP: Guiding Algorithm Discovery for Combinatorial Optimization Problems in an Experience World

cs.LG cs.AI ·2026-10-27 ·Kuan Xu, Jianming Wang, Ni Zhang, Yaoxin Wu, Yong Wang +1 more
similarity 0.56
Abstract

Large language models (LLMs) enable algorithm discovery for combinatorial optimization problems (COPs) through iterative program generation and evaluation. A central challenge is how to organize search to discover better algorithms within a limited budget. Our key insight is that past search trajectories and their recorded outcomes form an experience world, which can be used to facilitate the COP solving through replay. We introduce Dream-COP, in which a \emph{policy agent} learns executable policies through \emph{dreaming} in this experience world to guide a \emph{discovery agent} in generating and refining COP programs. Specifically, policy replay provides feedback on the quality of the programs revealed and the search steps used, to guide policy selection more effectively. Across five COPs, \textsc{Dream} discovers better algorithms than fixed exploration in both heuristic component design and complete solver generation. Particularly, it matches the optimal values on KP and reduces the gap on OBPP from 2.112\% to 1.199\% while using 42.5\% fewer search requests. Moreover, the learned exploration policies transfer effectively across different COPs with the assitance of the experience world.

0.19

Harness-S: Learning from Sibling Harnesses for Generalizable Agent Training

cs.AI ·2026-11-03 ·Kangning Zhang, Wenxiang Jiao, Bowen Fang, Shuai Shao, Jiachen Zhu +6 more
code/datacommunity pick similarity 0.55
Abstract · Code: https://github.com/DeepExperience/Harness-S; Keywords: Language model agents, agent harnesses, reinforcement learning, harness complem…

Harness evolution from a common base exhibits Locality, Complementarity, and Nonstationarity: variants repair different failures, and their utility changes as the policy learns. Rather than seeking a universally superior harness, we introduce Harness-S to selectively rescue failures of a base execution system through sibling harnesses and transfer the resulting capabilities into a single policy that remains effective under the original harness. Directional Harness Evolution develops specialized sibling harnesses along distinct repair directions, forming a reusable Sibling Harness Pool that remains fixed during policy training. Complementary Harness Rescue Training invokes this pool only when all initial attempts under the base harness fail. The same policy generates fresh rollouts under selected auxiliary harnesses, and these trajectories replace the failed group for reinforcement learning. An Adaptive Harness Router selects the Top-k variants using Harness Behavior Profiles and voting across multiple LLMs. Policy-aware profile re-anchoring refreshes this evidence as the policy learns. Across AppWorld, SWE-Gym, and DBBench, the trained policy substantially outperforms policy-only training when returned to the original base harness. Behavioral analyses and held-out cases support the transfer of harness-elicited behaviors into the policy itself. Reusing the router for Rank-1 inference provides additional gains at the same executor rollout count.

0.28

VeruSteer: Learning What to Repair Next in Verus

cs.SE ·2026-10-21 ·Chao Jiang, Ding Wang, Chaohua Yang, Dugang Liu, Zhiwu Xu +5 more
similarity 0.55
Abstract

LLM-based verification systems repair Rust proofs by revising programs in response to Verus diagnostics. When several error types are reported, pipelines such as AutoVerus and VeruSAGE select the next repair target using a preset priority. Yet each repair changes the program and the errors that follow, so the same reported types can require different choices at different states. We present VeruSteer, which learns to select error types from the outcomes of alternative repair trajectories. It constructs repair trees offline and compares paths from the same initial program by verification success, repair rounds, and final verification progress. These comparisons supervise a selector that combines step-wise imitation with trajectory preference ranking. The selector uses self-attention over the program, verifier feedback, and earlier selections to rank the currently reported types. It replaces the default priority within a single repair trajectory, keeping the existing repair agents and adding no repair or verifier calls for selection. We evaluate VeruSteer by replaying its choices on stored AutoVerus and VeruSAGE test trees under four generation configurations. Across 1,270 test trees, VeruSteer increases verified outcomes from 185 to 194 (14.57\% to 15.28\%), gaining 12 successes and losing three for a net improvement of 0.71 percentage points. Among trees where the default fails but a recorded alternative verifies, VeruSteer succeeds on 3 of 4 AutoVerus trees and 9 of 11 VeruSAGE trees. Among trees with recorded alternatives where the default verifies, it retains success on 14 of 15 AutoVerus trees and 12 of 14 VeruSAGE trees. It also finds shorter successful trajectories and improves final progress on some trees where all recorded trajectories fail.

0.12

Local Solution Repair for Multi-Agent Pickup and Delivery

cs.RO cs.MA ·2026-11-01 ·Ethan Schneider, Jingkai Chen, Seth Hutchinson, Sonia Chernova
similarity 0.54
Abstract

Multi-robot systems in automated warehouses must efficiently attend to a constant stream of pickup-and-delivery tasks while avoiding collisions. Existing Multi-Agent Pickup-and-Delivery (MAPD) solutions generate plans that are globally feasible but often locally inefficient. In large-scale, long-horizon deployments, these inefficiencies, such as robots backtracking from target goal locations and idling in congested areas, accumulate over time and degrade performance. This paper contributes Local Solution Repair (LSR), a goal replanning approach that detects suboptimal behaviors at run-time and locally improves plans to reduce conflict between agents. We demonstrate the utility of our approach by repairing solutions generated by state-of-the-art MAPD baselines, M2M and LNS-PBS. Our results in long-horizon warehouse simulations over three environments show upwards of 5.9% improvement in task throughput over current state-of-the-art methods by reducing the number of suboptimal instances by ~36k or by 14.6% with minor additional computation time.

0.12

Evolutionary Giant Tour for CVRP using NSE and ML Heuristic]{Evolutionary Giant Tour approach for CVRP using Node Shift Encoding and Machine Learning repair heuristic

cs.NE ·2026-10-01 ·Souad Abdoune, Menouar Boulif
benchmark similarity 0.54
Abstract · 21 pages, 16 figures

The Capacitated Vehicle Routing Problem (CVRP) remains a central concern in logistics research, as route optimisation under rigid capacity and fleet restrictions directly affects operational performance. Genetic Algorithms are widely used for this problem, yet their effectiveness depends heavily on the choice of solution encoding and on the mechanisms used to preserve feasibility during the search. This paper proposes a sequential framework that separates the evolutionary process from route construction. We adapt Node Shift Encoding (NSE) to the CVRP giant-tour setting and benchmark it against Path Representation and Double Chromosome. We further propose an unsupervised machine-learning repair heuristic that restores fleet feasibility after an unconstrained linear split, and compare this pipeline against fleet-constrained split taken from the literature. Computational tests on standard benchmark instances show that NSE consistently outperforms the other encodings in solution quality and feasibility. The repair heuristic restores feasibility in approximately 72\% of cases, and the Linear-Split-ML-Heuristic pipeline proves more robust than the constrained split, delivering lower costs and higher feasibility rates.

0.28

L2R-EV: Learning What to Repair in Electric Ride-Pooling with Finite Charger Queues

cs.GT ·2026-09-30 ·Mai Pham, Vikrant S. Vaze, Peter Chin
similarity 0.54
Abstract

Electric ride-pooling must jointly manage passenger service, routes, batteries, and finite chargers; a locally useful relocation can reduce later service. We introduce a discrete-event ride-pooling simulator with ordered passenger stops, pickup and ride-time constraints, battery reserves, charger travel, and finite first-come, first-served (FCFS) charging queues. On top of a common dispatcher, we add a learned repair layer that moves uncollected passengers between vehicles, uses a supervised score to estimate later effects, and uses a two-stage proximal-policy-optimization (PPO) policy to focus computation on promising moves. Every executed move must satisfy route, battery, and time constraints and provide an immediate route-cost improvement. For larger instances, we limit the number of candidate moves and apply several non-conflicting repairs at once. On 12 held-out Manhattan episodes with 100 requests, 30 EVs, and one plug per station, supervised repair reduces operational cost by 6.57\% versus no repair (12/12 wins) and serves 74.92 rather than 72.75 requests. Two-stage PPO stays within 1.43\% of supervised repair with 95.4\% fewer exact trials, while our experiments scale to 8,000 requests and 2,400 EVs with cost reductions across all three larger development settings. Queue-aware charging reduces waiting by 41.0\%; under a declared 1.5-kW queue-idle load, operational electricity per served request falls 1.73\%.

0.19