mlsanityData to 7 Oct 2026

Learning Large Neighborhood Search Policy for Integer Programming

arXiv 2111.03466 ↗First posted 1 Nov 2021cs.AI cs.LG math.OCcited by 35

Not on the map. Why?

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.

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

Builds on

27 of 48 references.

References · 27

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  3. 2018Relational inductive biases, deep learning, and graph networkscited by 1,341
  4. 2015Pointer Networkscited by 882
  5. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 751
  6. 2018Attention, Learn to Solve Routing Problems!cited by 646
  7. 2018Learning Dexterous In-Hand Manipulationcited by 643
  8. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  9. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 600
  10. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
  11. 2018Graph Convolutional Networks for Text Classificationcited by 345
  12. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 313
15 more
  1. 2018Learning to Perform Local Rewriting for Combinatorial Optimizationcited by 183
  2. 2020Solving Mixed Integer Programs Using Neural Networkscited by 178
  3. 2019Learning Improvement Heuristics for Solving Routing Problemscited by 162
  4. 2015Deep Reinforcement Learning in Large Discrete Action Spacescited by 158
  5. 2020Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learningcited by 139
  6. 2019Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problemcited by 117
  7. 2019Reinforcement Learning for Integer Programming: Learning to Cutcited by 108
  8. 2020Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problemscited by 100
  9. 2017Action Branching Architectures for Deep Reinforcement Learningcited by 90
  10. 2021Learning and Planning in Complex Action Spacescited by 76
  11. 2019Learning Action Representations for Reinforcement Learningcited by 75
  12. 2019Discretizing Continuous Action Space for On-Policy Optimizationcited by 65
  13. 2021Heterogeneous Attentions for Solving Pickup and Delivery Problem via Deep Reinforcement Learningcited by 35
  14. 2021Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problemcited by 31
  15. 2020Learn to Design the Heuristics for Vehicle Routing Problemcited by 24

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 4; 2023: 7; 2024: 7; 2025: 9; 2026: 8.

35 papers.

Sort:

By area:

  1. 2023GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-timecited by 82
  2. 2023DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimizationcited by 77
  3. 2022A Survey for Solving Mixed Integer Programming via Machine Learningcited by 44
  4. 2023Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learningcited by 37
  5. 2024Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programmingcited by 24
  6. 2025Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programmingcited by 16
  7. 2024Distributional MIPLIB: a Multi-Domain Library for Advancing ML-Guided MILP Methodscited by 15
  8. 2024Rethinking the Capacity of Graph Neural Networks for Branching Strategycited by 12
  9. 2023Learning To Dive In Branch And Boundcited by 10
  10. 2024SORREL: Suboptimal-Demonstration-Guided Reinforcement Learning for Learning to Branchcited by 9
  11. 2025MOTIF: Multi-strategy Optimization via Turn-based Interactive Frameworkcited by 7
  12. 2022DOGE-Train: Discrete Optimization on GPU with End-to-end Trainingcited by 6
23 more
  1. 2022Online Control of Adaptive Large Neighborhood Search using Deep Reinforcement Learningcited by 5
  2. 2022Local Branching Relaxation Heuristics for Integer Linear Programscited by 4
  3. 2023A Neural Separation Algorithm for the Rounded Capacity Inequalitiescited by 4
  4. 2023A Hierarchical Destroy and Repair Approach for Solving Very Large-Scale Travelling Salesman Problemcited by 4
  5. 2024Discretizing Continuous Action Space with Unimodal Probability Distributions for On-Policy Reinforcement Learningcited by 4
  6. 2024Balans: Multi-Armed Bandits-based Adaptive Large Neighborhood Search for Mixed-Integer Programming Problemcited by 4
  7. 2025CoCo-MILP: Inter-Variable Contrastive and Intra-Constraint Competitive MILP Solution Predictioncited by 4
  8. 2025RoME: Domain-Robust Mixture-of-Experts for MILP Solution Prediction across Domainscited by 3
  9. 2025FORGE: Foundational Optimization Representations from Graph Embeddingscited by 2
  10. 2023Data-driven Mixed Integer Optimization through Probabilistic Multi-variable Branchingcited by 1
  11. 2024RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programscited by 1
  12. 2025ParBalans: Parallel Multi-Armed Bandits-based Adaptive Large Neighborhood Searchcited by 1
  13. 2025SPL-LNS: Sampling-Enhanced Large Neighborhood Search for Solving Integer Linear Programscited by 1
  14. 2026A General Neural Backbone for Mixed-Integer Linear Optimization via Dual Attentioncited by 1
  15. 2026Large Neighborhood Search meets Iterative Neural Constraint Heuristicscited by 1
  16. 2025XXt Can Be Fastercited by 0
  17. 2025HyP-ASO: A Hybrid Policy-based Adaptive Search Optimization Framework for Large-Scale Integer Linear Programscited by 0
  18. 2026Towards Solving Polynomial-Objective Integer Programming with Hypergraph Neural Networkscited by 0
  19. 2026Solving Integer Linear Programming with Parallel Temperingcited by 0
  20. 2026Machine Learning-Enhanced Tabu Search for Tactical Wireless Network Designcited by 0
  21. 2026SPO: Discovering Adaptive Large Neighborhood Search Operators via Stackelberg Program Optimizationcited by 0
  22. 2026BiFE: Search-Efficient Discovery of CPU-Only Branching Policies via LLM-based Bi-Fidelity Evolutioncited by 0
  23. 2026GeoNest: Learning to Select Failure-Aware Neighborhoods for the Irregular Knapsack Problem in a Circular Containercited by 0