Finding Backdoors to Integer Programs: A Monte Carlo Tree Search
  Framework
  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.
