Search papers, labs, and topics across Lattice.
This paper introduces regularized large neighborhood search (RLNS), a novel approach that transforms the traditional LNS heuristic into an efficient MCMC sampler for NP-hard combinatorial problems. By incorporating entropic regularization, RLNS enables exact block Gibbs sampling and allows for a flexible interpolation between pseudolikelihood and exact maximum likelihood estimation. The method is validated through applications in $k$-subset selection, generalized assignment, and stochastic vehicle scheduling, showcasing its effectiveness in scenarios where exact solutions are computationally infeasible.
RLNS turns a classic heuristic into a powerful MCMC sampler, enabling efficient combinatorial optimization without the need for exact solutions.
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.
DeepMind
Google Research