REVIEW 21 cited by
An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
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
An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
read the original abstract
This paper introduces a new learning-based approach for approximately solving the Travelling Salesman Problem on 2D Euclidean graphs. We use deep Graph Convolutional Networks to build efficient TSP graph representations and output tours in a non-autoregressive manner via highly parallelized beam search. Our approach outperforms all recently proposed autoregressive deep learning techniques in terms of solution quality, inference speed and sample efficiency for problem instances of fixed graph sizes. In particular, we reduce the average optimality gap from 0.52% to 0.01% for 50 nodes, and from 2.26% to 1.39% for 100 nodes. Finally, despite improving upon other learning-based approaches for TSP, our approach falls short of standard Operations Research solvers.
Forward citations
Cited by 21 Pith papers
-
TSP with Predictions: Heatmap to Tour with Provable Guarantees
Any TSP heatmap of L1 error η yields a tour of cost ≤ OPT + 2η via a prediction-biased Christofides algorithm, with matching near-linear variants and experiments.
-
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.
-
Regularized Large Neighborhood Search
RLNS regularizes LNS to perform block Gibbs sampling under entropy, interpolating between pseudolikelihood and exact MLE for differentiable combinatorial optimization.
-
SPACE: Unifying Symmetric and Asymmetric Routing Problems for Generalist Neural Solver
SPACE framework unifies symmetric and asymmetric VRPs via bidirectional Frechet representations and weight-decomposed decoding for zero-shot generalization across 110 variants.
-
Memory-Guided Tree Search with Cross-Branch Knowledge Transfer for LLM Solver Synthesis
MEMOIR adds branch-local and global memory with a reflection step to tree search for LLM solver synthesis, reaching 96.7% solution validity and 7.3-point score gains over baselines on seven CO problems with lower run-...
-
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.
-
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...
-
GeoRouteNet: A Geometry-Aware Non-Autoregressive Neural Solver for the Euclidean Traveling Salesman Problem
GeoRouteNet improves non-autoregressive neural TSP solvers via geometric inductive biases and MCS-RL training, reporting 0.32% gap on TSP50, 1.26% on TSP100, and 3.60% on TSPLIB instances with higher throughput than C...
-
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.
-
Towards Generalization-Oriented Models for Vehicle Routing Problems with Mixture-of-Experts
R2E-IG combines residual refined experts with instance-level gating and mixed-distribution training using dynamic weight adaptation to improve generalization of DRL solvers for vehicle routing problems.
-
Convex Compositional Reasoning Models
CCEM parameterizes compositional factors with input-convex neural networks and optimizes the summed energy over a convex relaxation, allowing models trained on small instances to transfer to larger ones.
-
GOAL: Graph-based Objective-Aligned Diffusion Solvers for Dynamic Multi-Objective Optimization
GOAL uses conditioned diffusion on relational graphs with typed edges to produce feasible multi-objective solutions for scheduling problems, reporting 100% feasibility and sub-0.2% MAPE on FSP, JSP, and FJSP up to 20 jobs.
-
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.
-
Network Interdiction Goes Neural
Multipartite GNN learns MILP formulations of network interdiction to outperform baselines on bi-level combinatorial tasks.
-
Output-Constrained Decision Trees
Presents three new training procedures for regression trees that enforce convex output constraints at training time and validates them on synthetic and hierarchical time-series data.
-
Convex Compositional Reasoning Models
CCEM parameterizes compositional energy factors with input-convex neural networks and optimizes over a convex relaxation to enable deterministic scaling from small to large combinatorial reasoning instances.
-
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.
-
Empowering Targeted Neighborhood Search via Hyper Tour for Large-Scale TSP
HyperNS clusters TSP cities with a sparse heatmap, builds a hyper tour over supernodes, and restricts neighborhood search to hyper-tour-relevant edges to improve solution quality on large instances.
-
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.
-
GES-TSP: Graph Edge Sparsification for TSP
GES uses Delaunay coarse graphs, hand-crafted edge features, and a GAT to sparsify Euclidean TSP instances, pruning ~95–99% of edges with sub-1% optimality gaps on MATILDA and TSPLIB.
-
Supplementary Materials to Graph Convolutional Branch and Bound
Supplementary results on 1-tree relaxation performance inside a GCN-augmented branch-and-bound solver for TSP.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.