Learning Backdoors for Mixed Integer Linear Programs with Contrastive Learning
Many real-world problems can be efficiently modeled as Mixed Integer Linear Programs (MILPs) and solved with the Branch-and-Bound method. Prior work has shown the existence of MILP 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 the highest-ranked backdoor candidate. 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 several common MILP problem domains, demonstrates performance improvements over both Gurobi and previous models.
Code (0)
등록된 구현이 없습니다.
Tasks
Contrastive LearningGraph AttentionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Finding Backdoors to Integer Programs: A Monte Carlo Tree Search Framework
In Mixed Integer Linear Programming (MIP), a (strong) backdoor is a "small" subset of an instance's integer variables with the following property: in a branch-and-bound procedure, the instance can be solved to global opt…
Learning Pseudo-Backdoors for Mixed Integer Programs
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…
Combinatorial OptimizationLearning for Online Mixed-Integer Model Predictive Control with Parametric Optimality Certificates
We propose a supervised learning framework for computing solutions of multi-parametric Mixed Integer Linear Programs (MILPs) that arise in Model Predictive Control. Our approach also quantifies sub-optimality for the com…
Model Predictive ControlMotion PlanningReLU Networks as Surrogate Models in Mixed-Integer Linear Programs
We consider the embedding of piecewise-linear deep neural networks (ReLU networks) as surrogate models in mixed-integer linear programming (MILP) problems. A MILP formulation of ReLU networks has recently been applied by…
ML-Guided Primal Heuristics for Mixed Binary Quadratic Programs
Mixed Binary Quadratic Programs (MBQPs) are an important and complex set of problems in combinatorial optimization. As solving large-scale combinatorial optimization problems is challenging, primal heuristics have been d…