Learning Pseudo-Backdoors for Mixed Integer Programs
  We propose a machine learning approach for quickly solving Mixed Integer
Programs (MIP) by learning to prioritize a set of decision variables, which we
call pseudo-backdoors, for branching that results in faster solution times.
Learning-based approaches have seen success in the area of solving
combinatorial optimization problems by being able to flexibly leverage common
structures in a given distribution of problems. Our approach takes inspiration
from the concept of strong backdoors, which corresponds to a small set of
variables such that only branching on these variables yields an optimal
integral solution and a proof of optimality. Our notion of pseudo-backdoors
corresponds to a small set of variables such that only branching on them leads
to faster solve time (which can be solver dependent). A key advantage of
pseudo-backdoors over strong backdoors is that they are much amenable to
data-driven identification or prediction. Our proposed method learns to
estimate the solver performance of a proposed pseudo-backdoor, using a labeled
dataset collected on a set of training MIP instances. This model can then be
used to identify high-quality pseudo-backdoors on new MIP instances from the
same distribution. We evaluate our method on the generalized independent set
problems and find that our approach can efficiently identify high-quality
pseudo-backdoors. In addition, we compare our learned approach against Gurobi,
a state-of-the-art MIP solver, demonstrating that our method can be used to
improve solver performance.
