# SPL-LNS: Sampling-Enhanced Large Neighborhood Search for Solving Integer Linear Programs

arXiv: https://arxiv.org/abs/2508.16171 · HTML: https://mlsanity.com/paper/2508.16171/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 39 references that are in the map.
- First posted on arXiv 22 Aug 2025.

## Builds on (most cited first, 9 of 9)

- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [Learning to Schedule Heuristics in Branch-and-Bound](https://mlsanity.com/paper/2103.10294/) (2021)
- [Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs](https://mlsanity.com/paper/2107.10201/) (2021)
- [Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning](https://mlsanity.com/paper/2302.01578/) (2023)
- [Learning Large Neighborhood Search Policy for Integer Programming](https://mlsanity.com/paper/2111.03466/) (2021)
- [Regularized Langevin Dynamics for Combinatorial Optimization](https://mlsanity.com/paper/2502.00277/) (2025)
- [Alternative Mixed Integer Linear Programming Optimization for Joint Job Scheduling and Data Allocation in Grid Computing](https://mlsanity.com/paper/2502.00261/) (2025)

## Built on by (most cited first, 1 of 1)

- [Large Neighborhood Search meets Iterative Neural Constraint Heuristics](https://mlsanity.com/paper/2603.20801/) (2026)

## Abstract (arXiv)

Large Neighborhood Search (LNS) is a common heuristic in combinatorial optimization that iteratively searches over a large neighborhood of the current solution for a better one. Recently, neural network-based LNS solvers have achieved great success in solving Integer Linear Programs (ILPs) by learning to greedily predict the locally optimal solution for the next neighborhood proposal. However, this greedy approach raises two key concerns: (1) to what extent this greedy proposal suffers from local optima, and (2) how can we effectively improve its sample efficiency in the long run. To address these questions, this paper first formulates LNS as a stochastic process, and then introduces SPL-LNS, a sampling-enhanced neural LNS solver that leverages locally-informed proposals to escape local optima. We also develop a novel hindsight relabeling method to efficiently train SPL-LNS on self-generated data. Experimental results demonstrate that SPL-LNS substantially surpasses prior neural LNS solvers for various ILP problems of different sizes.