← Back to all news
arXiv AI

A First Guess Is Rarely the Final Answer: Learned Local Search That Generalizes to Larger Routing Problems

The paper introduces NICO, a learned 2‑opt local search policy for routing problems that improves upon initial neural solutions by repeatedly applying local moves. NICO addresses three shortcomings of prior policies—incumbent representation, input feature scaling, and move‑gain computation—by using edge‑based tokens without positional encodings, scale‑free features, and exact move gains added to logits. Experiments show that NICO generalizes to larger instances, achieving a 1.1% gap on 1000‑node Euclidean TSP and outperforming both greedy 2‑opt and previous learned policies, while also enhancing tours from constructive and diffusion‑based solvers on road‑network and CVRP benchmarks.

Related stories

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 AI
Oct 27

From Comparison to Selection: Enhancing Cross-Scale Generalization of Pointer Networks Trained with Reinforcement Learning for Capacitated Vehicle Routing Problem

The paper investigates why attention-based Pointer Networks, though size‑agnostic, lose performance when applied to different sized Capacitated Vehicle Routing Problems (CVRP). It identifies three causes—node‑density shifts, attention dispersion, and diluted graph context—and evaluates architectural changes on both encoder and decoder sides, including a learned permutation‑invariant graph‑context aggregation. The authors show that entropy‑based attention scaling improves large‑to‑small transfer, while the new aggregation methods best aid small‑to‑large transfer, and they combine these insights into a selector that chooses the optimal model for each train‑test size pair, reducing costs by up to 3.2% across seen and many unseen sizes.

By Sofiene Lassoued, Devara Tertia, Stefan Lier, Andreas Schwung
reinforcement-learning
More like this →
arXiv Machine Learning
Aug 14

RoutePack: Expert Placement and Attention-Aware Data Packing for MoE Reinforcement Learning

arXiv:2608. 12146v1 Announce Type: cross Abstract: Training Mixture-of-Experts (MoE) models for reinforcement learning (RL) couples two load-balancing problems: sequence composition determines dense attention work in each data-parallel microbatch, while token routing determines sparse expert work on expert-parallel ranks.

By Yibo Shen, Xudong Han, Xiaowei Zhu, Gen Li, Zhenxuan Pan
reinforcement-learningefficiency
More like this →
arXiv Machine Learning
4d ago

What We Keep of What We Forget: Replacement Operators and Routing Semantics in Training-Free MoE Expert Pruning

The paper investigates training‑free pruning of Mixture‑of‑Experts (MoE) models, focusing on how to handle the computation when a router selects a pruned expert. It compares replacement operators from three families on several models (OLMoE, DeepSeek‑V2‑Lite, Moonlight, Granite) while keeping the pruning mask fixed, and introduces a new operator called the tilted novice. The study finds that no single operator consistently dominates, with performance varying by model, pruning level, and evaluation metric, and it proposes a five‑item checklist for reporting results.

By Ezza Ali, Sehrish Bibi, Momina Moetesum, Faisal Shafait
efficiency
More like this →