# Finding Backdoors to Integer Programs: A Monte Carlo Tree Search Framework

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 38 references that are in the map.
- First posted on arXiv 16 Oct 2021.

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

- [Solving NP-Hard Problems on Graphs with Extended AlphaGo Zero](https://mlsanity.com/paper/1905.11623/) (2019)
- [A Comparison of Monte Carlo Tree Search and Mathematical Optimization for Large Scale Dynamic Resource Allocation](https://mlsanity.com/paper/1405.5498/) (2014)
- [First-Order Problem Solving through Neural MCTS based Reinforcement Learning](https://mlsanity.com/paper/2101.04167/) (2021)

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

- [Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming](https://mlsanity.com/paper/2402.05501/) (2024)
- [Distributional MIPLIB: a Multi-Domain Library for Advancing ML-Guided MILP Methods](https://mlsanity.com/paper/2406.06954/) (2024)
- [Multi-task Representation Learning for Mixed Integer Linear Programming](https://mlsanity.com/paper/2412.14409/) (2024)
- [Learning Backdoors for Mixed Integer Linear Programs with Contrastive Learning](https://mlsanity.com/paper/2401.10467/) (2024)
- [UNSAT Solver Synthesis via Monte Carlo Forest Search](https://mlsanity.com/paper/2211.12581/) (2022)
- [Layered and Staged Monte Carlo Tree Search for SMT Strategy Synthesis](https://mlsanity.com/paper/2401.17159/) (2024)
- [Machine Learning for K-adaptability in Two-stage Robust Optimization](https://mlsanity.com/paper/2210.11152/) (2022)
- [AlphaMapleSAT: An MCTS-based Cube-and-Conquer SAT Solver for Hard Combinatorial Problems](https://mlsanity.com/paper/2401.13770/) (2024)
- [Machine Learning for Combinatorial Optimisation of Partially-Specified Problems: Regret Minimisation as a Unifying Lens](https://mlsanity.com/paper/2205.10157/) (2022)
- [LEO: Learning Efficient Orderings for Multiobjective Binary Decision Diagrams](https://mlsanity.com/paper/2307.03171/) (2023)
- [An Efficient Algorithm for Thresholding Monte Carlo Tree Search](https://mlsanity.com/paper/2601.22600/) (2026)
- [Fusing Backdoors, Machine Learning, and Optimization for Large-Scale Parametric Mixed-Integer Programs](https://mlsanity.com/paper/2606.21440/) (2026)

## Abstract (arXiv)

In Mixed Integer Linear Programming (MIP), a (strong) backdoor is a "small" subset of an instance's integer variables with the following property: in a branch-and-bound procedure, the instance can be solved to global optimality by branching only on the variables in the backdoor. Constructing datasets of pre-computed backdoors for widely used MIP benchmark sets or particular problem families can enable new questions around novel structural properties of a MIP, or explain why a problem that is hard in theory can be solved efficiently in practice. Existing algorithms for finding backdoors rely on sampling candidate variable subsets in various ways, an approach which has demonstrated the existence of backdoors for some instances from MIPLIB2003 and MIPLIB2010. However, these algorithms fall short of consistently succeeding at the task due to an imbalance between exploration and exploitation. We propose BaMCTS, a Monte Carlo Tree Search framework for finding backdoors to MIPs. Extensive algorithmic engineering, hybridization with traditional MIP concepts, and close integration with the CPLEX solver have enabled our method to outperform baselines on MIPLIB2017 instances, finding backdoors more frequently and more efficiently.