mlsanityData to 14 Oct 2026

Latent Guided Sampling for Combinatorial Optimization

arXiv 2506.03672 ↗First posted 4 Jun 2025stat.ML cs.LG math.OCcited by 0

Not on the map. Why?

Abstract (arXiv)

Combinatorial Optimization problems are widespread in domains such as logistics, manufacturing, and drug discovery, yet their NP-hard nature makes them computationally challenging. Recent Neural Combinatorial Optimization (NCO) methods leverage deep learning to learn policies for constructing solutions, trained via Supervised or Reinforcement Learning. While promising, these approaches often rely on task-specific augmentations, perform poorly on out-of-distribution instances, and lack robust inference mechanisms. Moreover, existing latent space models either require labeled data or use an instance-independent latent distribution. In this work, we propose LGS-Net, a novel latent space model that conditions on problem instances, and introduce an efficient inference method, Latent Guided Sampling (LGS), based on Markov Chain Monte Carlo and Stochastic Approximation. We show that the iterations of our method form a time-inhomogeneous Markov Chain and provide rigorous theoretical convergence guarantees. Empirical results on benchmark routing tasks show that our method achieves state-of-the-art performance among NCO baselines.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 54 of its 108 references that are in the map. First posted on arXiv 4 Jun 2025.

Builds on

54 of 108 references.

References · 54

  1. 2017Attention Is All You Needcited by 60,361
  2. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  3. 2020Denoising Diffusion Probabilistic Modelscited by 21,076
  4. 2021High-Resolution Image Synthesis with Latent Diffusion Modelscited by 18,863
  5. 2020Score-Based Generative Modeling through Stochastic Differential Equationscited by 9,122
  6. 2015Deep Unsupervised Learning using Nonequilibrium Thermodynamicscited by 7,058
  7. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,885
  8. 2014Sequence to Sequence Learning with Neural Networkscited by 2,986
  9. 2017Arbitrary Style Transfer in Real-time with Adaptive Instance Normalizationcited by 2,010
  10. 2020Big Bird: Transformers for Longer Sequencescited by 1,684
  11. 2015Pointer Networkscited by 895
  12. 2016Automatic chemical design using a data-driven continuous representation of moleculescited by 765
38 more
  1. 2018Attention, Learn to Solve Routing Problems!cited by 656
  2. 2015Generating Sentences from a Continuous Spacecited by 612
  3. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 608
  4. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  5. 2015Importance Weighted Autoencoderscited by 456
  6. 2023DPOK: Reinforcement Learning for Fine-tuning Text-to-Image Diffusion Modelscited by 450
  7. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 348
  8. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 333
  9. 2021GFlowNet Foundationscited by 290
  10. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 269
  11. 2018Learning to Perform Local Rewriting for Combinatorial Optimizationcited by 185
  12. 2020Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instancescited by 162
  13. 2023Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalizationcited by 142
  14. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 129
  15. 2020Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhoodcited by 125
  16. 2019Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problemcited by 117
  17. 2021Learning to Delegate for Large-scale Vehicle Routingcited by 109
  18. 2018Stochastic Variance-Reduced Policy Gradientcited by 106
  19. 2020Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problemscited by 100
  20. 2021Efficient Active Search for Combinatorial Optimization Problemscited by 100
  21. 2020Learning the Travelling Salesperson Problem Requires Rethinking Generalizationcited by 98
  22. 2024Understanding Reinforcement Learning-Based Fine-Tuning of Diffusion Models: A Tutorial and Reviewcited by 98
  23. 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
  24. 2021Matrix Encoding Networks for Neural Combinatorial Optimizationcited by 91
  25. 2021Learning Collaborative Policies to Solve NP-hard Routing Problemscited by 86
  26. 2022Simulation-guided Beam Search for Neural Combinatorial Optimizationcited by 84
  27. 2023DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimizationcited by 78
  28. 2024Amortizing intractable inference in diffusion models for vision, language, and controlcited by 72
  29. 2023Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policycited by 62
  30. 2022Winner Takes It All: Training Performant RL Populations for Combinatorial Optimizationcited by 58
  31. 2018Accurate and Diverse Sampling of Sequences based on a "Best of Many" Sample Objectivecited by 56
  32. 2024Ant Colony Sampling with GFlowNets for Combinatorial Optimizationcited by 53
  33. 2019Non-asymptotic Analysis of Biased Stochastic Approximation Schemecited by 45
  34. 2023Combinatorial Optimization with Policy Adaptation using Latent Space Searchcited by 41
  35. 2025Rethinking Light Decoder-based Solvers for Vehicle Routing Problemscited by 37
  36. 2024PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimizationcited by 35
  37. 2020On the Convergence Theory of Debiased Model-Agnostic Meta-Reinforcement Learningcited by 19
  38. 2025Adversarial Generative Flow Network for Solving Vehicle Routing Problemscited by 10

50 most cited of 54 All 54 (JSON)

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement
  2. 2024A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization
  3. 2024Take a Step and Reconsider: Sequence Decoding for Self-Improved Neural Combinatorial Optimization
  4. 2025ASAP: Exploiting the Satisficing Generalization Edge in Neural Combinatorial Optimization
  5. 2024DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problems
  6. 2022Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch
  7. 2025Generative Modeling for Robust Deep Reinforcement Learning on the Traveling Salesman Problem
  8. 2025Boosting Cross-problem Generalization in Diffusion-Based Neural Combinatorial Solver via Inference Time Adaptation