Research map / Graph learning / Graph algorithms and clustering
Learning to Solve NP-Complete Problems: A Graph Neural Network for Decision TSP
Marcelo Prates, Pedro H. C. Avelar, Henrique Lemos, Luis C. Lamb, Moshe Y. Vardi
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train with paired decision examples at ±2% of the optimum | GNN-TSP · Decision TSP, test (n=20–40) | accuracy: 80% | Improved |
| Increase the decision-cost deviation from 2% to 5% or 10% | GNN-TSP · Decision TSP, test (n=20–40) | accuracy: 80 -> 98; 80 -> 100 | Improved |
| Reduce the decision-cost deviation from 2% to 1% | GNN-TSP · Decision TSP, test (n=20–40) | accuracy: 80 -> 66 | Hurt |
| Apply the model to random metric rather than Euclidean graphs | GNN-TSP · Decision TSP, 2% deviation | accuracy: 80 -> 64 | Hurt |
| Apply the model to non-metric random graphs | GNN-TSP · Decision TSP, random graphs | accuracy: 50 | Hurt |
| Increase instance size beyond the training range | GNN-TSP · Decision TSP, larger instances | accuracy: 50% | Hurt |
| Increase deviation for larger instances | GNN-TSP · Decision TSP, larger instances | accuracy: >95% | Improved |
| Add ±100%, +200%, and +1000% examples in a one-epoch retraining pass | GNN-TSP · Decision TSP, test accuracy | accuracy | No clear effect |
| Use binary search over target costs with the trained decision model | GNN-TSP · Route cost prediction, test (n=20–40) | absolute deviation: 1.5% | Improved |
| Use the trained model rather than Nearest Neighbor or Simulated Annealing as a decision predictor | GNN-TSP · Decision TSP, tested deviations | true positive rate: >90% TPR from deviations 4% and above | Improved |
| Use GNN-TSP rather than Simulated Annealing for TSPLIB route-cost estimation | GNN-TSP with binary search · TSPLIB instances | absolute relative deviation: 6 out of 9 | Mixed |
Closest papers by meaning
- BIPNN: Learning to Solve Binary Integer Programming via Hypergraph Neural Networks (NeurIPS 2025 · similarity 0.87)
- Are Graph Neural Networks Optimal Approximation Algorithms? (NeurIPS 2024 · similarity 0.87)
- On the Power of Small-size Graph Neural Networks for Linear Programming (NeurIPS 2024 · similarity 0.87)
- Neural Solver Selection for Combinatorial Optimization (ICML 2025 · similarity 0.87)
- Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs (ICML 2025 · similarity 0.86)
- COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems (AAAI 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
