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
![]() |
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: |
| ||||||
ORCID: |
| ||||||
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