Research map / Learning theory and algorithms / Combinatorial and search optimization

Regularized Large Neighborhood Search

NeurIPS 2026 · Learning theory and algorithms › Combinatorial and search optimization · approach: Heuristic and local search algorithms · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces regularized large neighborhood search (RLNS), which turns LNS into a block Gibbs / perturbed-LNS sampler for learning combinatorial layers with Fenchel-Young losses using only local oracles.

Problem

Training neural networks with combinatorial optimization layers requires a global exact or marginal solver, which is intractable for NP-hard OR problems; LNS heuristics lack a principled differentiable learning framework.

Approach

Regularize (entropic or perturbation-based) LNS subproblems so that the LNS Markov chain is a block Gibbs sampler of the global regularized distribution; the number of RLNS iterations K interpolates between pseudolikelihood (K=1) and exact maximum likelihood (K→∞) Fenchel-Young learning.

Key results

• On the GAP, RLNS with larger K better approximates global perturbed Fenchel-Young learning, and local MAP oracles are orders of magnitude faster than global ones at scale.
• On stochastic vehicle scheduling, RLNS-1 outperforms DBB and BCE in delay cost and nearly matches global PFY while solving a subproblem of about one-third the original size.
• RLNS achieves 100% acceptance rate and converges faster than Local Search MCMC on kappa-hot vector estimation.

Limitations

• Shannon regularization requires efficient local marginal oracles, which can be intractable even in restricted neighborhoods.
• Perturbation-based RLNS introduces structural bias into the stationary distribution.
• Bias bounds depend on constraint-graph cut sizes and are only bounds.

Experimental setup

Datasets: synthetic kappa-hot vector instances generalized assignment problem instances stochastic vehicle scheduling benchmark

Benchmarks: kappa-hot vector estimation generalized assignment problem stochastic vehicle scheduling

Metrics: mean absolute error test set MAE delay cost gradient variance oracle wall-clock time acceptance rate

Baselines: PFY (perturbed Fenchel-Young) DBB (blackbox differentiation) BCE Local Search MCMC i.i.d. Monte-Carlo estimation greedy expert policy

Builds on: Fenchel-Young losses perturbed optimizers (perturb-and-MAP) large neighborhood search pseudolikelihood Local search MCMC

Closest papers by meaning

• A General Large Neighborhood Search Framework for Solving Integer Linear Programs (NeurIPS 2020 · similarity 0.88)
• Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning (ICML 2023 · similarity 0.87)
• Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems (ICML 2025 · similarity 0.87)
• Process-Aware LNS for Large-Scale MILP via Context-Enhanced Fine-Tuned LLM-driven Selector (NeurIPS 2026 · similarity 0.87)
• Regularized Langevin Dynamics for Combinatorial Optimization (ICML 2025 · similarity 0.86)
• Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large Neighborhood Search (AAAI 2024 · similarity 0.85)