# Learning Large Neighborhood Search Policy for Integer Programming

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 48 references that are in the map.
- First posted on arXiv 1 Nov 2021.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [Learning Dexterous In-Hand Manipulation](https://mlsanity.com/paper/1808.00177/) (2018)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Graph Convolutional Networks for Text Classification](https://mlsanity.com/paper/1809.05679/) (2018)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [Learning Improvement Heuristics for Solving Routing Problems](https://mlsanity.com/paper/1912.05784/) (2019)
- [Deep Reinforcement Learning in Large Discrete Action Spaces](https://mlsanity.com/paper/1512.07679/) (2015)
- [Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning](https://mlsanity.com/paper/2010.12367/) (2020)
- [Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/1911.09539/) (2019)
- [Reinforcement Learning for Integer Programming: Learning to Cut](https://mlsanity.com/paper/1906.04859/) (2019)
- [Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2012.10638/) (2020)
- [Action Branching Architectures for Deep Reinforcement Learning](https://mlsanity.com/paper/1711.08946/) (2017)
- [Learning and Planning in Complex Action Spaces](https://mlsanity.com/paper/2104.06303/) (2021)
- [Learning Action Representations for Reinforcement Learning](https://mlsanity.com/paper/1902.00183/) (2019)
- [Discretizing Continuous Action Space for On-Policy Optimization](https://mlsanity.com/paper/1901.10500/) (2019)
- [Heterogeneous Attentions for Solving Pickup and Delivery Problem via Deep Reinforcement Learning](https://mlsanity.com/paper/2110.02634/) (2021)
- [Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/2110.02629/) (2021)
- [Learn to Design the Heuristics for Vehicle Routing Problem](https://mlsanity.com/paper/2002.08539/) (2020)

## Built on by (most cited first, 30 of 35)

- [GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time](https://mlsanity.com/paper/2312.08224/) (2023)
- [DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization](https://mlsanity.com/paper/2309.14032/) (2023)
- [A Survey for Solving Mixed Integer Programming via Machine Learning](https://mlsanity.com/paper/2203.02878/) (2022)
- [Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning](https://mlsanity.com/paper/2302.01578/) (2023)
- [Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming](https://mlsanity.com/paper/2402.05501/) (2024)
- [Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming](https://mlsanity.com/paper/2503.01129/) (2025)
- [Distributional MIPLIB: a Multi-Domain Library for Advancing ML-Guided MILP Methods](https://mlsanity.com/paper/2406.06954/) (2024)
- [Rethinking the Capacity of Graph Neural Networks for Branching Strategy](https://mlsanity.com/paper/2402.07099/) (2024)
- [Learning To Dive In Branch And Bound](https://mlsanity.com/paper/2301.09943/) (2023)
- [SORREL: Suboptimal-Demonstration-Guided Reinforcement Learning for Learning to Branch](https://mlsanity.com/paper/2412.15534/) (2024)
- [MOTIF: Multi-strategy Optimization via Turn-based Interactive Framework](https://mlsanity.com/paper/2508.03929/) (2025)
- [DOGE-Train: Discrete Optimization on GPU with End-to-end Training](https://mlsanity.com/paper/2205.11638/) (2022)
- [Online Control of Adaptive Large Neighborhood Search using Deep Reinforcement Learning](https://mlsanity.com/paper/2211.00759/) (2022)
- [Local Branching Relaxation Heuristics for Integer Linear Programs](https://mlsanity.com/paper/2212.08183/) (2022)
- [A Neural Separation Algorithm for the Rounded Capacity Inequalities](https://mlsanity.com/paper/2306.17283/) (2023)
- [A Hierarchical Destroy and Repair Approach for Solving Very Large-Scale Travelling Salesman Problem](https://mlsanity.com/paper/2308.04639/) (2023)
- [Discretizing Continuous Action Space with Unimodal Probability Distributions for On-Policy Reinforcement Learning](https://mlsanity.com/paper/2408.00309/) (2024)
- [Balans: Multi-Armed Bandits-based Adaptive Large Neighborhood Search for Mixed-Integer Programming Problem](https://mlsanity.com/paper/2412.14382/) (2024)
- [CoCo-MILP: Inter-Variable Contrastive and Intra-Constraint Competitive MILP Solution Prediction](https://mlsanity.com/paper/2511.09209/) (2025)
- [RoME: Domain-Robust Mixture-of-Experts for MILP Solution Prediction across Domains](https://mlsanity.com/paper/2511.02331/) (2025)
- [FORGE: Foundational Optimization Representations from Graph Embeddings](https://mlsanity.com/paper/2508.20330/) (2025)
- [Data-driven Mixed Integer Optimization through Probabilistic Multi-variable Branching](https://mlsanity.com/paper/2305.12352/) (2023)
- [RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programs](https://mlsanity.com/paper/2411.19517/) (2024)
- [ParBalans: Parallel Multi-Armed Bandits-based Adaptive Large Neighborhood Search](https://mlsanity.com/paper/2508.06736/) (2025)
- [SPL-LNS: Sampling-Enhanced Large Neighborhood Search for Solving Integer Linear Programs](https://mlsanity.com/paper/2508.16171/) (2025)
- [A General Neural Backbone for Mixed-Integer Linear Optimization via Dual Attention](https://mlsanity.com/paper/2601.04509/) (2026)
- [Large Neighborhood Search meets Iterative Neural Constraint Heuristics](https://mlsanity.com/paper/2603.20801/) (2026)
- [XXt Can Be Faster](https://mlsanity.com/paper/2505.09814/) (2025)
- [HyP-ASO: A Hybrid Policy-based Adaptive Search Optimization Framework for Large-Scale Integer Linear Programs](https://mlsanity.com/paper/2509.15828/) (2025)
- [Towards Solving Polynomial-Objective Integer Programming with Hypergraph Neural Networks](https://mlsanity.com/paper/2603.19318/) (2026)

## Abstract (arXiv)

We propose a deep reinforcement learning (RL) method to learn large neighborhood search (LNS) policy for integer programming (IP). The RL policy is trained as the destroy operator to select a subset of variables at each step, which is reoptimized by an IP solver as the repair operator. However, the combinatorial number of variable subsets prevents direct application of typical RL algorithms. To tackle this challenge, we represent all subsets by factorizing them into binary decisions on each variable. We then design a neural network to learn policies for each variable in parallel, trained by a customized actor-critic algorithm. We evaluate the proposed method on four representative IP problems. Results show that it can find better solutions than SCIP in much less time, and significantly outperform other LNS baselines with the same runtime. Moreover, these advantages notably persist when the policies generalize to larger problems. Further experiments with Gurobi also reveal that our method can outperform this state-of-the-art commercial solver within the same time limit.