Title: Regularized Large Neighborhood Search

Abstract: Large neighborhood search (LNS), a scalable heuristic that iteratively improves a solution by locally re-optimizing subsets of its variables, is the standard tool for operations research experts tackling NP-hard combinatorial problems. Conversely, most current methods for embedding combinatorial optimization layers into neural networks rely on access to exact global solutions, a requirement that is computationally infeasible. To address this discrepancy, we propose regularized LNS (RLNS). By introducing regularization or perturbation to local subproblems, RLNS transforms the LNS heuristic into an efficient Markov Chain Monte Carlo (MCMC) sampler across the combinatorial space of feasible solutions, accompanied by Fenchel-Young losses. We demonstrate that, under entropic regularization, RLNS executes exact block Gibbs sampling. Additionally, by varying the number of RLNS iterations, one can interpolate between pseudolikelihood and exact maximum likelihood estimation, enabling end-to-end learning without the need for global solvers. We validate our method on problems involving $k$-subset selection, generalized assignment, and stochastic vehicle scheduling.

Source: arXiv Generated at: 2026-06-02 00:00:00 UTC