# Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning

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

## 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 (most cited first, 30 of 36)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [Momentum Contrast for Unsupervised Visual Representation Learning](https://mlsanity.com/paper/1911.05722/) (2019)
- [Supervised Contrastive Learning](https://mlsanity.com/paper/2004.11362/) (2020)
- [Learning deep representations by mutual information estimation and maximization](https://mlsanity.com/paper/1808.06670/) (2018)
- [Graph Contrastive Learning with Augmentations](https://mlsanity.com/paper/2010.13902/) (2020)
- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (2021)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Contrastive Learning as Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2206.07568/) (2022)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [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)
- [Learning to Delegate for Large-scale Vehicle Routing](https://mlsanity.com/paper/2107.04139/) (2021)
- [NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem](https://mlsanity.com/paper/2110.07983/) (2021)
- [Hybrid Models for Learning to Branch](https://mlsanity.com/paper/2006.15212/) (2020)
- [Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies](https://mlsanity.com/paper/2002.05120/) (2020)
- [Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning](https://mlsanity.com/paper/2206.13414/) (2022)
- [Contrastive Losses and Solution Caching for Predict-and-Optimize](https://mlsanity.com/paper/2011.05354/) (2020)
- [Learning to Select Cuts for Efficient Mixed-Integer Programming](https://mlsanity.com/paper/2105.13645/) (2021)
- [Learning to Schedule Heuristics in Branch-and-Bound](https://mlsanity.com/paper/2103.10294/) (2021)
- [Learning to branch with Tree MDPs](https://mlsanity.com/paper/2205.11107/) (2022)
- [Ecole: A Gym-like Library for Machine Learning in Combinatorial Optimization Solvers](https://mlsanity.com/paper/2011.06069/) (2020)
- [Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs](https://mlsanity.com/paper/2107.10201/) (2021)
- [Learning Large Neighborhood Search Policy for Integer Programming](https://mlsanity.com/paper/2111.03466/) (2021)
- [Understanding Deep Contrastive Learning via Coordinate-wise Optimization](https://mlsanity.com/paper/2201.12680/) (2022)
- [Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem](https://mlsanity.com/paper/2012.04461/) (2020)

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

- [A Cookbook of Self-Supervised Learning](https://mlsanity.com/paper/2304.12210/) (2023)
- [Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming](https://mlsanity.com/paper/2402.05501/) (2024)
- [MILP-StuDio: MILP Instance Generation via Block Structure Decomposition](https://mlsanity.com/paper/2410.22806/) (2024)
- [Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs](https://mlsanity.com/paper/2406.05938/) (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)
- [FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2505.16952/) (2025)
- [SORREL: Suboptimal-Demonstration-Guided Reinforcement Learning for Learning to Branch](https://mlsanity.com/paper/2412.15534/) (2024)
- [Learning to Optimize for Mixed-Integer Non-linear Programming with Feasibility Guarantees](https://mlsanity.com/paper/2410.11061/) (2024)
- [Multi-task Representation Learning for Mixed Integer Linear Programming](https://mlsanity.com/paper/2412.14409/) (2024)
- [Learning-Guided Rolling Horizon Optimization for Long-Horizon Flexible Job-Shop Scheduling](https://mlsanity.com/paper/2502.15791/) (2025)
- [AI4OPT: AI Institute for Advances in Optimization](https://mlsanity.com/paper/2307.02671/) (2023)
- [Learning Backdoors for Mixed Integer Linear Programs with Contrastive Learning](https://mlsanity.com/paper/2401.10467/) (2024)
- [Learning to Segment for Vehicle Routing Problems](https://mlsanity.com/paper/2507.01037/) (2025)
- [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)
- [Adaptive Stabilization Based on Machine Learning for Column Generation](https://mlsanity.com/paper/2405.11198/) (2024)
- [mRNA2vec: mRNA Embedding with Language Model in the 5'UTR-CDS for mRNA Design](https://mlsanity.com/paper/2408.09048/) (2024)
- [RoME: Domain-Robust Mixture-of-Experts for MILP Solution Prediction across Domains](https://mlsanity.com/paper/2511.02331/) (2025)
- [Accelerating data-driven algorithm selection for combinatorial partitioning problems](https://mlsanity.com/paper/2402.14332/) (2024)
- [Principled Data Augmentation for Learning to Solve Quadratic Programming Problems](https://mlsanity.com/paper/2506.01728/) (2025)
- [FORGE: Foundational Optimization Representations from Graph Embeddings](https://mlsanity.com/paper/2508.20330/) (2025)
- [RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programs](https://mlsanity.com/paper/2411.19517/) (2024)
- [Code Retrieval for MILP Instance Generation](https://mlsanity.com/paper/2505.11526/) (2025)
- [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)
- [ID-PaS+ : Identity-Aware Predict-and-Search for General Mixed-Integer Linear Programs](https://mlsanity.com/paper/2512.10211/) (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)
- [HyP-ASO: A Hybrid Policy-based Adaptive Search Optimization Framework for Large-Scale Integer Linear Programs](https://mlsanity.com/paper/2509.15828/) (2025)

## 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.