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
An efficient graph convolutional network technique for the travelling salesman problem
17 Pith papers cite this work. Polarity classification is still indexing.
17
Pith papers citing it
hub tools
citation-role summary
background 1
citation-polarity summary
roles
background 1polarities
background 1representative citing papers
RLNS regularizes LNS to perform block Gibbs sampling under entropy, interpolating between pseudolikelihood and exact MLE for differentiable combinatorial optimization.
SPACE framework unifies symmetric and asymmetric VRPs via bidirectional Frechet representations and weight-decomposed decoding for zero-shot generalization across 110 variants.
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-to-run variance.
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.
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.
A geometry-enhanced non-autoregressive neural TSP solver with multi-candidate RL cuts the TSPLIB optimality gap from 17.12% to 3.60% while solving in milliseconds per instance.
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.
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.
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.
Multipartite GNN learns MILP formulations of network interdiction to outperform baselines on bi-level combinatorial tasks.
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.
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.
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.
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.
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.
Supplementary results on 1-tree relaxation performance inside a GCN-augmented branch-and-bound solver for TSP.
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.
-
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-to-run variance.
-
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 simulations up to 56 qubits on synthetic, molecular, and TSP datasets.
-
GeoRouteNet: A Geometry-Aware Non-Autoregressive Neural Solver for the Euclidean Traveling Salesman Problem
A geometry-enhanced non-autoregressive neural TSP solver with multi-candidate RL cuts the TSPLIB optimality gap from 17.12% to 3.60% while solving in milliseconds per instance.
-
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.
-
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.
-
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.
-
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.