mlsanityData to 14 Oct 2026

Learning for Dynamic Combinatorial Optimization without Training Data

arXiv 2505.19497 ↗First posted 26 May 2025cs.LGcited by 1

Not on the map. Why?

Abstract (arXiv)

We introduce DyCO-GNN, a novel unsupervised learning framework for Dynamic Combinatorial Optimization that requires no training data beyond the problem instance itself. DyCO-GNN leverages structural similarities across time-evolving graph snapshots to accelerate optimization while maintaining solution quality. We evaluate DyCO-GNN on dynamic maximum cut, maximum independent set, and the traveling salesman problem across diverse datasets of varying sizes, demonstrating its superior performance under tight and moderate time budgets. DyCO-GNN consistently outperforms the baseline methods, achieving high-quality solutions up to 3-60x faster, highlighting its practical effectiveness in rapidly evolving resource-constrained settings.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 29 of its 57 references that are in the map. First posted on arXiv 26 May 2025.

Builds on

29 of 57 references.

References · 29

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  3. 2017Graph Attention Networkscited by 8,923
  4. 2017Inductive Representation Learning on Large Graphscited by 6,320
  5. 2015Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classificationcited by 3,611
  6. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,434
  7. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,089
  8. 2015Pointer Networkscited by 895
  9. 2018Attention, Learn to Solve Routing Problems!cited by 656
  10. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 608
  11. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  12. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 318
17 more
  1. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 269
  2. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 221
  3. 2013Ising formulations of many NP problemscited by 207
  4. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 129
  5. 2020Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphscited by 115
  6. 2021Combinatorial Optimization with Physics-Inspired Graph Neural Networkscited by 108
  7. 2020Learning the Travelling Salesperson Problem Requires Rethinking Generalizationcited by 98
  8. 2021Graph Neural Network Guided Local Search for the Traveling Salesperson Problemcited by 70
  9. 2019Graph Neural Networks for Maximum Constraint Satisfactioncited by 46
  10. 2025Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimizationcited by 45
  11. 2022One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfactioncited by 27
  12. 2023Variational Annealing on Graphs for Combinatorial Optimizationcited by 21
  13. 2023Unsupervised Learning for Combinatorial Optimization Needs Meta-Learningcited by 20
  14. 2023Controlling Continuous Relaxation for Combinatorial Optimizationcited by 16
  15. 2023Distributed Constrained Combinatorial Optimization leveraging Hypergraph Neural Networkscited by 13
  16. 2023Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketchingcited by 4
  17. 2018Fully Dynamic Maximal Independent Set with Sublinear Update Timecited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Test-Time Adaptation for Unsupervised Combinatorial Optimizationcited by 0