Finding Backdoors to Integer Programs: A Monte Carlo Tree Search Framework
This work addresses a specific challenge in optimization for researchers and practitioners in operations research, but it is incremental as it builds on existing sampling-based approaches with algorithmic improvements.
The authors tackled the problem of finding backdoors in Mixed Integer Linear Programming (MIP) instances, which are small subsets of variables that allow efficient solving via branch-and-bound, and their method, BaMCTS, outperformed baselines on MIPLIB2017 instances by finding backdoors more frequently and efficiently.
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.