Regularized Large Neighborhood Search
2026-06-01 • Machine Learning
Machine Learning
AI summaryⓘ
The authors present a new method called regularized large neighborhood search (RLNS) that improves how hard combinatorial problems are solved inside neural networks. Instead of needing an exact perfect solution, which is often impossible to get, their method tweaks smaller parts of the problem and uses a smart sampling process to explore good solutions. They prove their approach matches a known sampling technique under certain conditions and can smoothly switch between different learning methods without relying on global solvers. They tested this on several example problems like selecting groups and scheduling vehicles.
large neighborhood searchcombinatorial optimizationNP-hard problemsMarkov chain Monte Carlo (MCMC)Fenchel-Young lossblock Gibbs samplingentropic regularizationmaximum likelihood estimationpseudolikelihood estimationneural networks
Authors
Germain Vivier-Ardisson, Laurent Demonet, Axel Parmentier, Mathieu Blondel
Abstract
Operations research practitioners typically tackle NP-hard combinatorial problems using large neighborhood search (LNS), a scalable heuristic that iteratively refines a current solution by locally re-optimizing subsets of its variables. In contrast, most existing approaches for integrating combinatorial optimization layers into neural networks still assume access to an exact global solution, which is computationally intractable. We bridge this gap by introducing regularized LNS (RLNS). By regularizing or perturbing local subproblems, we turn the LNS heuristic into an efficient MCMC sampler over the combinatorial set of feasible solutions, with associated Fenchel-Young losses. Under entropic regularization, we prove that RLNS performs exact block Gibbs sampling. Furthermore, adjusting the number of RLNS iterations allows us to interpolate between pseudolikelihood and exact maximum likelihood estimation, for end-to-end learning without global solvers. We demonstrate our approach on $k$-subset selection, generalized assignment, and stochastic vehicle scheduling problems.