Regularized Large Neighborhood Search

• URL: http://arxiv.org/abs/2606.02294v1
• Date: Mon, 01 Jun 2026 14:16:18 GMT
• Title: Regularized Large Neighborhood Search
• Abstract summary: Operations research practitioners typically tackle NP-hard problems using large neighborhood search (LNS)<n>We bridge this gap by regularized LNS (RLNS)<n>Undertropic regularization, we prove that RLNS performs exact block Gibbs sampling.
• Score: 11.54620327711825
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Support Discovery With Iteratively Reweighted Least Squares for Fixed-Charge Network Flow [8.021197489470756]
  The fixed-charge network flow problem (FCNFP) couples continuous flow allocation with discrete arc-activation decisions.<n>We propose a scalable continuous-optimization FCNFP based on an iteratively reweighted least-squares framework.
  arXiv  Detail & Related papers  (2026-09-08T18:00:10Z)
• Don't Be Greedy, Just Relax! Pruning LLMs via Frank-Wolfe [61.68406997155879]
  State-of-the-art Large Language Model (LLM) pruning methods operate layer-wise, minimizing the per-layer pruning error on a small dataset to avoid full retraining.<n>Existing methods hence rely on greedy convexs that ignore the weight interactions in the pruning objective.<n>Our method drastically reduces the per-layer pruning error, outperforms strong baselines on state-of-the-art GPT architectures, and remains memory-efficient.
  arXiv  Detail & Related papers  (2025-10-15T16:13:44Z)
• HyP-ASO: A Hybrid Policy-based Adaptive Search Optimization Framework for Large-Scale Integer Linear Programs [29.446016007712114]
  HyP-ASO is a hybrid policy-based adaptive search optimization framework that combines a customized formula with deep Reinforcement Learning (RL)<n>Experiments demonstrate that HyP-ASO significantly outperforms existing LNS-based approaches for large-scale ILPs.<n>Additional experiments show it is lightweight and highly scalable, making it well-suited for solving large-scale ILPs.
  arXiv  Detail & Related papers  (2025-09-19T09:59:52Z)
• SPL-LNS: Sampling-Enhanced Large Neighborhood Search for Solving Integer Linear Programs [59.91461374628034]
  Large Neighborhood Search (LNS) is a common in optimization that iteratively searches over a large neighborhood of the current solution for a better one.<n>This paper introduces SPL-LNS, a sampling-enhanced neural LNS solver that leverages locally-informed proposals to escape local optima.
  arXiv  Detail & Related papers  (2025-08-22T07:49:33Z)
• Learning with Local Search MCMC Layers [12.613397606663801]
  We introduce a theoretically-principled approach for learning with inexact solvers.<n>We transform problem-specific neighborhood systems used in local searchs into proposal distributions.<n>We demonstrate our approach on a large-scale dynamic vehicle routing problem with time windows.
  arXiv  Detail & Related papers  (2025-05-20T11:47:42Z)
• Reinforcement learning with combinatorial actions for coupled restless bandits [62.89013331120493]
  We propose SEQUOIA, an RL algorithm that directly optimize for long-term reward over the feasible action space.<n>We empirically validate SEQUOIA on four novel restless bandit problems with constraints: multiple interventions, path constraints, bipartite matching, and capacity constraints.
  arXiv  Detail & Related papers  (2025-03-01T21:25:21Z)
• A Random-Key Optimizer for Combinatorial Optimization [0.0]
  This paper introduces a versatile and efficient local search method tailored for optimization problems.<n>Using the random-key concept, RKO encodes solutions as vectors of random keys that are subsequently decoded into feasible solutions.<n>The RKO framework is able to combine a plethora of classic metaheuristics, each capable of operating independently or in parallel, with solution sharing facilitated through an elite solution pool.
  arXiv  Detail & Related papers  (2024-11-06T22:23:29Z)
• Ant Colony Sampling with GFlowNets for Combinatorial Optimization [68.84985459701007]
  Generative Flow Ant Colony Sampler (GFACS) is a novel meta-heuristic method that hierarchically combines amortized inference and parallel search.<n>Our method first leverages Generative Flow Networks (GFlowNets) to amortize a emphmulti-modal prior distribution over solution space.<n>This prior is updated via parallel search in the spirit of Ant Colony Optimization (ACO) leading to the posterior distribution that generates near-optimal solutions.
  arXiv  Detail & Related papers  (2024-03-11T16:26:06Z)
• Large Scale Constrained Clustering With Reinforcement Learning [1.3597551064547502]
  Given a network, allocating resources at clusters level, rather than at each node, enhances efficiency in resource allocation and usage. We propose an approach to solve this constrained clustering problem via reinforcement learning. In the results section, we show that our algorithm finds near optimal solutions, even for large scale instances.
  arXiv  Detail & Related papers  (2024-02-15T18:27:18Z)
• Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learning [58.91954425047425]
  This paper aims to design a new gradient coding scheme for mitigating partial stragglers in distributed learning. We propose a gradient coordinate coding scheme with L coding parameters representing L possibly different diversities for the L coordinates, which generates most gradient coding schemes.
  arXiv  Detail & Related papers  (2022-06-06T09:25:40Z)
• Improved Training of Physics-Informed Neural Networks with Model Ensembles [81.38804205212425]
  We propose to expand the solution interval gradually to make the PINN converge to the correct solution. All ensemble members converge to the same solution in the vicinity of observed data. We show experimentally that the proposed method can improve the accuracy of the found solution.
  arXiv  Detail & Related papers  (2022-04-11T14:05:34Z)
• Improved Acyclicity Reasoning for Bayesian Network Structure Learning with Constraint Programming [0.0]
  Learning the structure of a Bayesian network (BNSL) from discrete data is known to be an NP-hard task. In this work, we propose a new time algorithm for discovering a subset of all possible cluster cuts. We show that, despite being suboptimal, they improve performance by orders of magnitude. The resulting solver also compares favourably with GOBNILP, a state-of-the-art solver for the BNSL problem.
  arXiv  Detail & Related papers  (2021-06-23T09:46:11Z)
• DeepSplit: Scalable Verification of Deep Neural Networks via Operator Splitting [70.62923754433461]
  Analyzing the worst-case performance of deep neural networks against input perturbations amounts to solving a large-scale non- optimization problem. We propose a novel method that can directly solve a convex relaxation of the problem to high accuracy, by splitting it into smaller subproblems that often have analytical solutions.
  arXiv  Detail & Related papers  (2021-06-16T20:43:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.