CaltechAUTHORS
  A Caltech Library Service

Learning Pseudo-Backdoors for Mixed Integer Programs

Ferber, Aaron and Song, Jialin and Dilkina, Bistra and Yue, Yisong (2021) Learning Pseudo-Backdoors for Mixed Integer Programs. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20210719-210128990

[img] PDF - Submitted Version
See Usage Policy.

77kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20210719-210128990

Abstract

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.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/2106.05080arXivDiscussion Paper
ORCID:
AuthorORCID
Dilkina, Bistra0000-0002-6784-473X
Yue, Yisong0000-0001-9127-1989
Additional Information:© 2021, Association for the Advancement of Artificial Intelligence.
Record Number:CaltechAUTHORS:20210719-210128990
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20210719-210128990
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:109916
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:19 Jul 2021 22:24
Last Modified:19 Jul 2021 22:24

Repository Staff Only: item control page