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.
hub
Attention, Learn to Solve Routing Problems!
25 Pith papers cite this work, alongside 192 external citations. Polarity classification is still indexing.
25
Pith papers citing it
192
external citations · Pith
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.
hub tools
citation-role summary
background 2
citation-polarity summary
roles
background 2polarities
background 2representative citing papers
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 outperforming prior samplers in 3D and 4D.
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.
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-shot to unseen scales.
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.
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.
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 simulations up to 56 qubits on synthetic, molecular, and TSP datasets.
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.
GRPO matches POMO solution quality within 2% on TSP/CVRP while avoiding REINFORCE training collapse on TSP-100 without needing a rollout baseline.
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.
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.
Reinforcement learning policy for qubit mapping reduces SWAP overhead by 65-85% versus standard quantum compilers on MQTBench and Queko benchmark circuits.
ECO combines a Mamba encoder-decoder with two-stage batched DPO and LS-aware preference construction, claiming the best reported neural performance and near-linear memory scaling on TSP up to 5000 nodes and CVRP up to 1000 nodes.
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.
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.
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.
A DRL cooperative router, YAML mission API, PX4/ROS 2 stacks, and online rendezvous-aware replanner cut energy-margin violations from 83% to 20% and support outdoor UAV–UGV field missions.
N(CO)^2 applies reinforcement learning with chance constraints to solve stochastic orienteering problems, generalizing across instances with performance competitive to MILP.
Fine-tuned LLMs with DAR sampling and DPO outperform off-the-shelf versions on algorithm design tasks and generalize to related settings.
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.
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 instead of hours.
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.
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.
Adding simulated annealing to random reconstruction and beam search to POMO in neural CVRP solvers reduces optimality gaps on standard benchmarks.
citing papers explorer
-
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 outperforming prior samplers in 3D and 4D.
-
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-shot to unseen scales.
-
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 simulations up to 56 qubits on synthetic, molecular, and TSP datasets.
-
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.
-
Rethinking Efficiency in Neural Combinatorial Optimization: Batched Preference Optimization with Mamba
ECO combines a Mamba encoder-decoder with two-stage batched DPO and LS-aware preference construction, claiming the best reported neural performance and near-linear memory scaling on TSP up to 5000 nodes and CVRP up to 1000 nodes.
-
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.
-
Towards Reliable Aerial Ground Vehicle Collaboration: An Integrated Planning and Autonomy Framework for Field Deployment
A DRL cooperative router, YAML mission API, PX4/ROS 2 stacks, and online rendezvous-aware replanner cut energy-margin violations from 83% to 20% and support outdoor UAV–UGV field missions.
-
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.
-
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.
-
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 instead of hours.
-
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.
-
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.