Learning pseudo-backdoors for mixed integer programs

DOI10.1007/978-3-031-08011-1_8zbMATH Open1502.90111arXiv2106.05080OpenAlexW3197542688MaRDI QIDQ2170189FDOQ2170189

Authors: Aaron Ferber, Jialin Song, Bistra Dilkina, Yisong Yue 

Publication date: 30 August 2022

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.

Full work available at URL: https://arxiv.org/abs/2106.05080

Recommendations

• On learning and branching: a survey
• Backdoor branching
• A machine learning-based approximation of strong branching
• Learning in search
• Learning a classification of mixed-integer quadratic programming problems

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Mixed integer programming (90C11)

Cites Work

• Paramils: an automatic algorithm configuration framework
• Title not available (Why is that?)
• Mixed integer programming: analyzing 12 years of progress
• Large margin methods for structured and interdependent output variables
• Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
• Backdoor branching
• A comparison of heuristics and relaxations for the capacitated plant location problem
• The generalized independent set problem: polyhedral analysis and solution approaches
• Decision diagrams for optimization
• Backdoors to Combinatorial Optimization: Feasibility and Optimality
• Backdoors in the Context of Learning
• Integer Programming
• An automatic method for solving discrete programming problems
• The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints
• Limitations of Restricted Branching in Clause Learning
• The effect of structural branching on the efficiency of clause learning SAT solving: An experimental study

Cited In (4)

• Ranking Constraint Relaxations for Mixed Integer Programs Using a Machine Learning Approach
• Learning a classification of mixed-integer quadratic programming problems
• A multi-agent learning framework for mixed-integer linear programming
• A Prescriptive Machine Learning Approach to Mixed-Integer Convex Optimization

Uses Software

• Paramils
• Gurobi
• PyTorch

This page was built for publication: Learning pseudo-backdoors for mixed integer programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2170189)