Latent Guided Sampling for Combinatorial Optimization

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.

Many important practical decision-making problems, such as planning delivery routes, organizing production, or searching for promising drug designs, require choosing the best solution from a very large number of possibilities. These problems can be extremely difficult to solve exactly, especially when the number of choices becomes large. Recent machine learning methods can learn to generate effective solutions, but they often depend on problem-specific tricks and may not work as well on unseen problem cases. In this paper, we introduce a new method that learns a problem-dependent latent search space, a learned representation that helps identify promising solutions. The method searches within this space and progressively moves toward better solutions under a practical inference budget. We also provide mathematical guarantees showing that the search procedure behaves in a controlled way. Experiments on standard routing problems show that our method finds high-quality solutions and improves over existing learning-based approaches.