mlsanityData to 7 Oct 2026

DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems

arXiv 2210.04123 ↗First posted 8 Oct 2022cs.LG cs.AI math.OCcited by 127

Not on the map. Why?

Abstract (arXiv)

Recently, deep reinforcement learning (DRL) models have shown promising results in solving NP-hard Combinatorial Optimization (CO) problems. However, most DRL solvers can only scale to a few hundreds of nodes for combinatorial optimization problems on graphs, such as the Traveling Salesman Problem (TSP). This paper addresses the scalability challenge in large-scale combinatorial optimization by proposing a novel approach, namely, DIMES. Unlike previous DRL methods which suffer from costly autoregressive decoding or iterative refinements of discrete solutions, DIMES introduces a compact continuous space for parameterizing the underlying distribution of candidate solutions. Such a continuous space allows stable REINFORCE-based training and fine-tuning via massively parallel sampling. We further propose a meta-learning framework to enable the effective initialization of model parameters in the fine-tuning stage. Extensive experiments show that DIMES outperforms recent DRL-based methods on large benchmark datasets for Traveling Salesman Problems and Maximal Independent Set problems.

Key facts. Cited by 127 papers in the map (data through 7 Oct 2026). Builds on 47 of its 90 references that are in the map. First posted on arXiv 8 Oct 2022.

Builds on

47 of 90 references.

References · 47

  1. 2017Attention Is All You Needcited by 59,932
  2. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  3. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  4. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  5. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  6. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 6,979
  7. 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,861
  8. 2013Auto-Encoding Variational Bayescited by 3,980
  9. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  10. 2018On First-Order Meta-Learning Algorithmscited by 1,003
  11. 2017Sigmoid-Weighted Linear Units for Neural Network Function Approximation in Reinforcement Learningcited by 935
  12. 2015Pointer Networkscited by 882
35 more
  1. 2018Attention, Learn to Solve Routing Problems!cited by 646
  2. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 600
  3. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
  4. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 341
  5. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 327
  6. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 265
  7. 2018Learning to Perform Local Rewriting for Combinatorial Optimizationcited by 183
  8. 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 182
  9. 2020Solving Mixed Integer Programs Using Neural Networkscited by 178
  10. 2019Learning Improvement Heuristics for Solving Routing Problemscited by 162
  11. 2020Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instancescited by 161
  12. 2020Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learningcited by 139
  13. 2019Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problemcited by 117
  14. 2020Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphscited by 115
  15. 2021Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformercited by 108
  16. 2021NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problemcited by 102
  17. 2020Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learningcited by 100
  18. 2020Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problemscited by 100
  19. 2021Efficient Active Search for Combinatorial Optimization Problemscited by 99
  20. 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
  21. 2021Matrix Encoding Networks for Neural Combinatorial Optimizationcited by 89
  22. 2021Learning Collaborative Policies to Solve NP-hard Routing Problemscited by 86
  23. 2019Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learningcited by 78
  24. 2020Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networkingcited by 70
  25. 2021Graph Neural Network Guided Local Search for the Traveling Salesperson Problemcited by 70
  26. 2020Learning What to Defer for Maximum Independent Setscited by 53
  27. 2020Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Timecited by 39
  28. 2022What's Wrong with Deep Learning in Tree Search for Combinatorial Optimizationcited by 36
  29. 2020Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problemcited by 31
  30. 2020A Deep Reinforcement Learning Algorithm Using Dynamic Attention Model for Vehicle Routing Problemscited by 30
  31. 2021A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphscited by 26
  32. 2019On Learning Paradigms for the Travelling Salesman Problemcited by 24
  33. 2021A Game-Theoretic Approach for Improving Generalization Ability of TSP Solverscited by 14
  34. 2021Improving Generalization of Deep Reinforcement Learning-based TSP Solverscited by 8
  35. 2022A Differentiable Approach to Combinatorial Optimization using Dataless Neural Networkscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 17; 2024: 36; 2025: 43; 2026: 31.

127 papers.

Sort:

By area:

  1. 2024Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Modelcited by 258
  2. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 216
  3. 2023Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalizationcited by 140
  4. 2023Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Optcited by 81
  5. 2023BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimizationcited by 80
  6. 2023DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimizationcited by 77
  7. 2023RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmarkcited by 70
  8. 2024MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Expertscited by 69
  9. 2023Towards Omni-generalizable Neural Methods for Vehicle Routing Problemscited by 68
  10. 2023Unsupervised Learning for Solving the Travelling Salesman Problemcited by 57
  11. 2024Ant Colony Sampling with GFlowNets for Combinatorial Optimizationcited by 53
  12. 2024INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformercited by 43
38 more
  1. 2025Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimizationcited by 43
  2. 2023Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNetscited by 40
  3. 2024How Efficient is LLM-Generated Code? A Rigorous & High-Standard Benchmarkcited by 39
  4. 2024GOAL: A Generalist Combinatorial Optimization Agent Learnercited by 39
  5. 2025Rethinking Light Decoder-based Solvers for Vehicle Routing Problemscited by 36
  6. 2024Self-Improved Learning for Scalable Neural Combinatorial Optimizationcited by 29
  7. 2024Learning to Handle Complex Constraints for Vehicle Routing Problemscited by 29
  8. 2025CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimizationcited by 28
  9. 2024Cross-Problem Learning for Solving Vehicle Routing Problemscited by 24
  10. 2024Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problemscited by 24
  11. 2023Meta-SAGE: Scale Meta-Learning Scheduled Adaptation with Guided Exploration for Mitigating Scale Shift on Combinatorial Optimizationcited by 23
  12. 2024Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectivescited by 23
  13. 2023Variational Annealing on Graphs for Combinatorial Optimizationcited by 21
  14. 2023Controlling Continuous Relaxation for Combinatorial Optimizationcited by 16
  15. 2025Generative Models in Decision Making: A Surveycited by 14
  16. 2025Learning to Reduce Search Space for Generalizable Neural Routing Solvercited by 14
  17. 2023Reconstructing Graph Diffusion History from a Single Snapshotcited by 13
  18. 2024DiffSG: A Generative Solver for Network Optimization with Diffusion Modelcited by 13
  19. 2024Diffusion Models as Network Optimizers: Explorations and Analysiscited by 13
  20. 2024Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimizationcited by 12
  21. 2025Breaking Silos: Adaptive Model Fusion Unlocks Better Time Series Forecastingcited by 12
  22. 2025Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learningcited by 12
  23. 2025Preference Optimization for Combinatorial Optimization Problemscited by 11
  24. 2024DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problemscited by 10
  25. 2024Matcha: Mitigating Graph Structure Shifts with Test-Time Adaptationcited by 10
  26. 2024Ask, and it shall be given: On the Turing completeness of promptingcited by 10
  27. 2025Regularized Langevin Dynamics for Combinatorial Optimizationcited by 10
  28. 2025Learning to Insert for Constructive Neural Vehicle Routing Solvercited by 10
  29. 2025FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimizationcited by 10
  30. 2025PLANETALIGN: A Comprehensive Python Library for Benchmarking Network Alignmentcited by 10
  31. 2023Adjustable Robust Reinforcement Learning for Online 3D Bin Packingcited by 9
  32. 2024Instance-Conditioned Adaptation for Large-scale Generalization of Neural Routing Solvercited by 9
  33. 2024Collaboration! Towards Robust Neural Methods for Routing Problemscited by 9
  34. 2023Benchmarking PtO and PnO Methods in the Predictive Combinatorial Optimization Regimecited by 8
  35. 2024Bridging Large Language Models and Optimization: A Unified Framework for Text-attributed Combinatorial Optimizationcited by 8
  36. 2025Graph Data Selection for Domain Adaptation: A Model-Free Approachcited by 7
  37. 2025URS: A Unified Neural Routing Solver for Cross-Problem Zero-Shot Generalizationcited by 7
  38. 2025Multi-Task Vehicle Routing Solver via Mixture of Specialized Experts under State-Decomposable MDPcited by 7

50 most cited of 127 All 127 (JSON)