Regularized Large Neighborhood Search

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Vivier-Ardisson, Germain, Demonet, Laurent, Parmentier, Axel, Blondel, Mathieu
Format:	Preprint
Published:	2026
Subjects:	Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

_version_	1866914623263866880
author	Vivier-Ardisson, Germain Demonet, Laurent Parmentier, Axel Blondel, Mathieu
author_facet	Vivier-Ardisson, Germain Demonet, Laurent Parmentier, Axel Blondel, Mathieu
contents	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.
format	Preprint
id	arxiv_https___arxiv_org_abs_2606_02294
institution	arXiv
publishDate	2026
record_format	arxiv
spellingShingle	Regularized Large Neighborhood Search Vivier-Ardisson, Germain Demonet, Laurent Parmentier, Axel Blondel, Mathieu Machine Learning 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.
title	Regularized Large Neighborhood Search
topic	Machine Learning
url	https://arxiv.org/abs/2606.02294