# Learning Backdoors for Mixed Integer Linear Programs with Contrastive Learning

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 47 references that are in the map.
- First posted on arXiv 19 Jan 2024.

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

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [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)
- [A Survey on Contrastive Self-supervised Learning](https://mlsanity.com/paper/2011.00362/) (2020)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [An efficient framework for learning sentence representations](https://mlsanity.com/paper/1803.02893/) (2018)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [Reinforcement Learning for Integer Programming: Learning to Cut](https://mlsanity.com/paper/1906.04859/) (2019)
- [Hybrid Models for Learning to Branch](https://mlsanity.com/paper/2006.15212/) (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 Schedule Heuristics in Branch-and-Bound](https://mlsanity.com/paper/2103.10294/) (2021)
- [A Survey for Solving Mixed Integer Programming via Machine Learning](https://mlsanity.com/paper/2203.02878/) (2022)
- [Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs](https://mlsanity.com/paper/2107.10201/) (2021)
- [A GNN-Guided Predict-and-Search Framework for Mixed-Integer Linear Programming](https://mlsanity.com/paper/2302.05636/) (2023)
- [Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning](https://mlsanity.com/paper/2302.01578/) (2023)
- [Learning to Compare Nodes in Branch and Bound with Graph Neural Networks](https://mlsanity.com/paper/2210.16934/) (2022)
- [Augment with Care: Contrastive Learning for Combinatorial Problems](https://mlsanity.com/paper/2202.08396/) (2022)
- [Learning to Search via Retrospective Imitation](https://mlsanity.com/paper/1804.00846/) (2018)
- [Finding Backdoors to Integer Programs: A Monte Carlo Tree Search Framework](https://mlsanity.com/paper/2110.08423/) (2021)
- [Learning Pseudo-Backdoors for Mixed Integer Programs](https://mlsanity.com/paper/2106.05080/) (2021)

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

- [FORGE: Foundational Optimization Representations from Graph Embeddings](https://mlsanity.com/paper/2508.20330/) (2025)
- [ID-PaS+ : Identity-Aware Predict-and-Search for General Mixed-Integer Linear Programs](https://mlsanity.com/paper/2512.10211/) (2025)
- [Fusing Backdoors, Machine Learning, and Optimization for Large-Scale Parametric Mixed-Integer Programs](https://mlsanity.com/paper/2606.21440/) (2026)
- [FunL2O: LLM-Guided Feature Function Design for Learning to Optimize](https://mlsanity.com/paper/2607.27389/) (2026)
- [BiFE: Search-Efficient Discovery of CPU-Only Branching Policies via LLM-based Bi-Fidelity Evolution](https://mlsanity.com/paper/2609.36735/) (2026)

## Abstract (arXiv)

Many real-world problems can be efficiently modeled as Mixed Integer Linear Programs (MILPs) and solved with the Branch-and-Bound method. Prior work has shown the existence of MILP backdoors, small sets of variables such that prioritizing branching on them when possible leads to faster running times. However, finding high-quality backdoors that improve running times remains an open question. Previous work learns to estimate the relative solver speed of randomly sampled backdoors through ranking and then decide whether to use the highest-ranked backdoor candidate. In this paper, we utilize the Monte-Carlo tree search method to collect backdoors for training, rather than relying on random sampling, and adapt a contrastive learning framework to train a Graph Attention Network model to predict backdoors. Our method, evaluated on several common MILP problem domains, demonstrates performance improvements over both Gurobi and previous models.