mlsanityData to 14 Oct 2026

Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning

arXiv 2302.01578 ↗First posted 3 Feb 2023cs.AIcited by 37

Not on the map. Why?

Abstract (arXiv)

Integer Linear Programs (ILPs) are powerful tools for modeling and solving a large number of combinatorial optimization problems. Recently, it has been shown that Large Neighborhood Search (LNS), as a heuristic algorithm, can find high quality solutions to ILPs faster than Branch and Bound. However, how to find the right heuristics to maximize the performance of LNS remains an open problem. In this paper, we propose a novel approach, CL-LNS, that delivers state-of-the-art anytime performance on several ILP benchmarks measured by metrics including the primal gap, the primal integral, survival rates and the best performing rate. Specifically, CL-LNS collects positive and negative solution samples from an expert heuristic that is slow to compute and learns a new one with a contrastive loss. We use graph attention networks and a richer set of features to further improve its performance.

Key facts. Cited by 37 papers in the map (data through 14 Oct 2026). Builds on 36 of its 84 references that are in the map. First posted on arXiv 3 Feb 2023.

Builds on

36 of 84 references.

References · 36

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2020A Simple Framework for Contrastive Learning of Visual Representationscited by 12,049
  3. 2018Representation Learning with Contrastive Predictive Codingcited by 7,777
  4. 2019Momentum Contrast for Unsupervised Visual Representation Learningcited by 7,513
  5. 2020Supervised Contrastive Learningcited by 2,829
  6. 2018Learning deep representations by mutual information estimation and maximizationcited by 1,273
  7. 2020Graph Contrastive Learning with Augmentationscited by 1,208
  8. 2021How Attentive are Graph Attention Networks?cited by 835
  9. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  10. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 318
  11. 2022Contrastive Learning as Goal-Conditioned Reinforcement Learningcited by 253
  12. 2018Learning a SAT Solver from Single-Bit Supervisioncited by 200
24 more
  1. 2018Learning to Perform Local Rewriting for Combinatorial Optimizationcited by 185
  2. 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 183
  3. 2019Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problemcited by 117
  4. 2019Reinforcement Learning for Integer Programming: Learning to Cutcited by 111
  5. 2021Learning to Delegate for Large-scale Vehicle Routingcited by 109
  6. 2021NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problemcited by 103
  7. 2020Hybrid Models for Learning to Branchcited by 95
  8. 2020Parameterizing Branch-and-Bound Search Trees to Learn Branching Policiescited by 63
  9. 2022Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learningcited by 61
  10. 2020Contrastive Losses and Solution Caching for Predict-and-Optimizecited by 52
  11. 2021Learning to Select Cuts for Efficient Mixed-Integer Programmingcited by 48
  12. 2021Learning to Schedule Heuristics in Branch-and-Boundcited by 46
  13. 2022Learning to branch with Tree MDPscited by 45
  14. 2020Ecole: A Gym-like Library for Machine Learning in Combinatorial Optimization Solverscited by 43
  15. 2021Learning a Large Neighborhood Search Algorithm for Mixed Integer Programscited by 43
  16. 2021Learning Large Neighborhood Search Policy for Integer Programmingcited by 35
  17. 2022Understanding Deep Contrastive Learning via Coordinate-wise Optimizationcited by 35
  18. 2020Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problemcited by 31
  19. 2022Learning to Compare Nodes in Branch and Bound with Graph Neural Networkscited by 31
  20. 2022Augment with Care: Contrastive Learning for Combinatorial Problemscited by 22
  21. 2020Learning to Resolve Conflicts for Multi-Agent Path Finding with Conflict-Based Searchcited by 7
  22. 2021Learning Pseudo-Backdoors for Mixed Integer Programscited by 5
  23. 2022Local Branching Relaxation Heuristics for Integer Linear Programscited by 4
  24. 2023Accelerating Multi-Agent Planning Using Graph Transformers with Bounded Suboptimalitycited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 2; 2024: 13; 2025: 14; 2026: 8.

37 papers.

Sort:

By area:

  1. 2023A Cookbook of Self-Supervised Learningcited by 250
  2. 2024Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programmingcited by 24
  3. 2024MILP-StuDio: MILP Instance Generation via Block Structure Decompositioncited by 17
  4. 2024Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programscited by 16
  5. 2025Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programmingcited by 16
  6. 2024Distributional MIPLIB: a Multi-Domain Library for Advancing ML-Guided MILP Methodscited by 15
  7. 2025FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimizationcited by 11
  8. 2024SORREL: Suboptimal-Demonstration-Guided Reinforcement Learning for Learning to Branchcited by 9
  9. 2024Learning to Optimize for Mixed-Integer Non-linear Programming with Feasibility Guaranteescited by 8
  10. 2024Multi-task Representation Learning for Mixed Integer Linear Programmingcited by 7
  11. 2025Learning-Guided Rolling Horizon Optimization for Long-Horizon Flexible Job-Shop Schedulingcited by 7
  12. 2023AI4OPT: AI Institute for Advances in Optimizationcited by 6
25 more
  1. 2024Learning Backdoors for Mixed Integer Linear Programs with Contrastive Learningcited by 5
  2. 2025Learning to Segment for Vehicle Routing Problemscited by 5
  3. 2024Balans: Multi-Armed Bandits-based Adaptive Large Neighborhood Search for Mixed-Integer Programming Problemcited by 4
  4. 2025CoCo-MILP: Inter-Variable Contrastive and Intra-Constraint Competitive MILP Solution Predictioncited by 4
  5. 2024Adaptive Stabilization Based on Machine Learning for Column Generationcited by 3
  6. 2024mRNA2vec: mRNA Embedding with Language Model in the 5'UTR-CDS for mRNA Designcited by 3
  7. 2025RoME: Domain-Robust Mixture-of-Experts for MILP Solution Prediction across Domainscited by 3
  8. 2024Accelerating data-driven algorithm selection for combinatorial partitioning problemscited by 2
  9. 2025Principled Data Augmentation for Learning to Solve Quadratic Programming Problemscited by 2
  10. 2025FORGE: Foundational Optimization Representations from Graph Embeddingscited by 2
  11. 2024RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programscited by 1
  12. 2025Code Retrieval for MILP Instance Generationcited by 1
  13. 2025ParBalans: Parallel Multi-Armed Bandits-based Adaptive Large Neighborhood Searchcited by 1
  14. 2025SPL-LNS: Sampling-Enhanced Large Neighborhood Search for Solving Integer Linear Programscited by 1
  15. 2025ID-PaS+ : Identity-Aware Predict-and-Search for General Mixed-Integer Linear Programscited by 1
  16. 2026A General Neural Backbone for Mixed-Integer Linear Optimization via Dual Attentioncited by 1
  17. 2026Large Neighborhood Search meets Iterative Neural Constraint Heuristicscited by 1
  18. 2025HyP-ASO: A Hybrid Policy-based Adaptive Search Optimization Framework for Large-Scale Integer Linear Programscited by 0
  19. 2025Machine Learning Guided Optimal Transmission Switching to Mitigate Wildfire Ignition Riskcited by 0
  20. 2026Imitation Learning for Combinatorial Optimisation under Uncertaintycited by 0
  21. 2026Learning to Solve Orienteering Problem with Time Windows and Variable Profitscited by 0
  22. 2026Solving Integer Linear Programming with Parallel Temperingcited by 0
  23. 2026Machine Learning-Enhanced Tabu Search for Tactical Wireless Network Designcited by 0
  24. 2026SPO: Discovering Adaptive Large Neighborhood Search Operators via Stackelberg Program Optimizationcited by 0
  25. 2026BiFE: Search-Efficient Discovery of CPU-Only Branching Policies via LLM-based Bi-Fidelity Evolutioncited by 0