Learning Backdoors for Mixed Integer Programs with Contrastive Learning
Junyang Cai Taoan Huang Bistra Dilkina
Many real-world problems can be efficiently modeled as Mixed Integer Programs
(MIPs) and solved with the Branch-and-Bound method. Prior work has shown the
existence of MIP backdoors, small sets of variables such that prioritizing
branching on them when possible leads to faster running times. However, finding
high-quality backdoors that improve running times remains an open question.
Previous work learns to estimate the relative solver speed of randomly sampled
backdoors through ranking and then decide whether to use it. In this paper, we
utilize the Monte-Carlo tree search method to collect backdoors for training,
rather than relying on random sampling, and adapt a contrastive learning
framework to train a Graph Attention Network model to predict backdoors. Our
method, evaluated on four common MIP problem domains, demonstrates performance
improvements over both Gurobi and previous models.