Learning pseudo-backdoors for mixed integer programs

DOI10.1007/978-3-031-08011-1_8MaRDI QIDQ2170189zbMATH OpenOpenAlexFDO

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

Publication date 30 August 2022

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

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)

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.

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

Cites work

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

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

Describes a project that uses

Uses Software

• PyTorch
• Gurobi
• Paramils

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)