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

Authors

  • Elias B. Khalil University of Toronto
  • Pashootan Vaezipoor University of Toronto Vector Institute for Artificial Intelligence
  • Bistra Dilkina University of Southern California

DOI:

https://doi.org/10.1609/aaai.v36i4.20293

Keywords:

Constraint Satisfaction And Optimization (CSO), Search And Optimization (SO)

Abstract

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.

Downloads

Published

2022-06-28

How to Cite

Khalil, E. B., Vaezipoor, P., & Dilkina, B. (2022). Finding Backdoors to Integer Programs: A Monte Carlo Tree Search Framework. Proceedings of the AAAI Conference on Artificial Intelligence, 36(4), 3786-3795. https://doi.org/10.1609/aaai.v36i4.20293

Issue

Section

AAAI Technical Track on Constraint Satisfaction and Optimization