REVIEW 26 cited by
Attention, Learn to Solve Routing Problems!
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Attention, Learn to Solve Routing Problems!
read the original abstract
The recently presented idea to learn heuristics for combinatorial optimization problems is promising as it can save costly development. However, to push this idea towards practical implementation, we need better models and better ways of training. We contribute in both directions: we propose a model based on attention layers with benefits over the Pointer Network and we show how to train this model using REINFORCE with a simple baseline based on a deterministic greedy rollout, which we find is more efficient than using a value function. We significantly improve over recent learned heuristics for the Travelling Salesman Problem (TSP), getting close to optimal results for problems up to 100 nodes. With the same hyperparameters, we learn strong heuristics for two variants of the Vehicle Routing Problem (VRP), the Orienteering Problem (OP) and (a stochastic variant of) the Prize Collecting TSP (PCTSP), outperforming a wide range of baselines and getting results close to highly optimized and specialized algorithms.
Forward citations
Cited by 26 Pith papers
-
Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming
Derives O(s^{1.5}/√N) generalization bound, Ω(s/√N) minimax lower bound, and shows SGA with averaging attains Θ(s/√N) optimal rate for data-driven Lagrangian relaxation in MILPs, plus faster Θ(s/N) rate for warm-start...
-
AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network
AGDN is a new GNN framework using a MixScore matrix and anisotropic graph diffusion to outperform prior methods on TSP instances across sizes and distributions.
-
TriSearch: Learning to Optimize Triangulations via Bistellar Flips
TriSearch is an RL framework that optimizes triangulations of polytopes using bistellar flips with a circuit-supported subtriangulation action representation, generalizing zero-shot to larger instances and outperformi...
-
Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming
Stochastic gradient ascent with averaging learns Lagrangian multipliers for MILP at the minimax rate Θ(s/√N) and faster Θ(s/N) for warm-start, closing the gap between upper and lower bounds.
-
Vehicle-as-Prompt: A Unified Deep Reinforcement Learning Framework for Heterogeneous Fleet Vehicle Routing Problem
VaP-CSMV uses a cross-semantic encoder and multi-view decoder to unify DRL solving of HFVRP variants, outperforming prior neural solvers while matching heuristics at much lower inference time and generalizing zero-sho...
-
Neural Certificate Pricing for Combinatorial Optimization Problems
NCP trains a neural network to predict certificate-level dual prices for CO problems, enabling structured primal recovery with a local second-order error guarantee when consistency holds.
-
Fairness Attacks on Recommender Systems
A structure-aware RL fairness attack with joint item and gender selection policies is introduced and shown effective on four recommender models across two datasets.
-
Scalable Message-Passing Quantum Graph Neural Networks in the Weisfeiler-Leman Hierarchy
The work constructs a permutation-equivariant quantum GNN that implements message passing at selectable Weisfeiler-Leman levels, supports pre-training on small graphs, and demonstrates readout scalability with simulat...
-
Vision-Assisted Foundation Model for Solving Multi-Task Vehicle Routing Problems
VaFM encodes constraint-specific VRP images via CNN into patch embeddings fused with graph nodes, using an auxiliary task to handle pixel imbalance, and reports better performance than prior methods on 16 VRP variants.
-
Baseline-Free Policy Optimization for Neural Combinatorial Optimization
GRPO matches POMO solution quality within 2% on TSP/CVRP while avoiding REINFORCE training collapse on TSP-100 without needing a rollout baseline.
-
MViewRouter: Internalizing Geometric Equivariance via Multi-view Alternating Attention for Combinatorial Routing
MViewRouter internalizes D4 geometric equivariance for routing via Multi-view Alternating Attention and Collective Policy Gradient Aggregation, yielding competitive solutions and strong generalization on TSP/CVRP benchmarks.
-
Learning Altruistic Collaboration in Heterogeneous Multi-Team Systems
A graph neural network learns to approximate altruistic robot transfers across heterogeneous teams using Hamilton's rule, achieving near-optimal allocation in simulated firefighting scenarios.
-
CO-MAP: A Reinforcement Learning Approach to the Qubit Allocation Problem
Reinforcement learning policy for qubit mapping reduces SWAP overhead by 65-85% versus standard quantum compilers on MQTBench and Queko benchmark circuits.
-
Machine Learning-based Two-Stage Graph Sparsification for the Travelling Salesman Problem
A two-stage ML sparsifier for TSP candidate graphs combines alpha-Nearest and POPMUSIC for high recall then trains a model to cut density while preserving coverage across distance types and instance sizes up to 500.
-
Rethinking Efficiency in Neural Combinatorial Optimization: Batched Preference Optimization with Mamba
ECO uses supervised warm-up plus iterative batched DPO on a Mamba backbone to reach top neural performance on TSP and CVRP while lowering memory growth and raising throughput.
-
Learning-Optimized Qubit Mapping and Reuse to Minimize Inter-Core Communication in Modular Quantum Architectures
QARMA applies transformer-augmented reinforcement learning to qubit allocation and reuse in modular quantum systems, reporting up to 86% average reduction in inter-core communications versus optimized Qiskit baselines.
-
Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Set
Classical solver KaMIS outperforms leading AI methods for Maximum Independent Set on random graphs, with some AI approaches no better than simple greedy heuristics and a new serialization analysis revealing similar reasoning.
-
Attention-Based Deep Reinforcement Learning for Qubit Allocation in Modular Quantum Architectures
An attention-based DRL agent with Transformer encoder and GNN learns heuristics for qubit-to-core allocation in multi-core quantum systems to minimize state transfers and online compilation time.
-
N(CO)$^2$: Neural Combinatorial Optimization with Chance Constraints to Solve Stochastic Orienteering
N(CO)^2 applies reinforcement learning with chance constraints to solve stochastic orienteering problems, generalizing across instances with performance competitive to MILP.
-
ARMATA: Auto-Regressive Multi-Agent Task Assignment
ARMATA is a new end-to-end autoregressive model with multi-stage decoding that unifies allocation and routing for multi-agent systems and reports up to 20% better solutions than OR-Tools, CPLEX, and LKH-3 in seconds i...
-
Machine Learning-based Two-Stage Graph Sparsification for the Travelling Salesman Problem
A two-stage ML pipeline unions α-Nearest and POPMUSIC candidate edges then prunes single-source edges via a classifier, cutting TSP graph density 37-47% with ≥99.69% optimal-tour recall.
-
Fine-tuning Large Language Model for Automated Algorithm Design
Fine-tuned LLMs with DAR sampling and DPO outperform off-the-shelf versions on algorithm design tasks and generalize to related settings.
-
RouteFormer: A Transformer-Based Routing Framework for Autonomous Vehicles
RouteFormer is a transformer-RL hybrid for single-agent graph routing that reports 10% and 7% shorter distances than Concorde and LKH-3 on mission-like graphs by incorporating constraints the solvers ignore.
-
Optimizing Nursing Care Taxi Dispatch Leveraging Integer Linear Programming Solvers and Machine Learning
A Transformer model trained via supervised learning on ILP solutions for a new nursing care taxi dispatch VRP variant reduces operating time by up to 8% on small instances while keeping constraint violations low.
-
NCO4CVRP: Neural Combinatorial Optimization for the Capacitated Vehicle Routing Problem
Adding simulated annealing to random reconstruction and beam search to POMO in neural CVRP solvers reduces optimality gaps on standard benchmarks.
-
Deep Learning for Sequential Decision Making under Uncertainty: Foundations, Frameworks, and Frontiers
A tutorial framing deep learning as a complement to optimization for sequential decision-making under uncertainty, with applications in supply chains, healthcare, and energy.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.