ECCO 2024
Abstract Submission

43. Learning to branch with interpretable machine learning models

Contributed abstract in session FB-2: Machine learning, stream Machine learning.

Friday, 10:30 - 12:00
Room: M228

Authors (first author is the speaker)

1. Nikolaos Sahinidis
Georgia Institute of Technology
2. Selin Bayramoglu
Industrial and Systems Engineering, Georgia Institute of Technology
3. George Nemhauser
Georgia Institute of Technology

Abstract

Machine learning is being increasingly used in improving decisions made within branch-and-bound algorithms for solving mixed-integer programs (MIPs). A common trend of existing works in this area is the utilization of deep learning techniques. The construction of learning models based on these methods requires massive computations to construct the very large datasets that are required for training. Additionally, the deployment of these learning models becomes practical only in conjunction with manycore parallelization (GPUs) for the calculation of the learned functions themselves. In this work, we depart from common practice and build simple and interpretable machine learning models. We demonstrate this approach in the context of approximating strong branching scores, a costly expert branching rule. Our method selects important features for a given problem domain and produces statistically significant models for the MIPs studied. We compare our models with built-in branching rules of SCIP, a state-of-the-art solver, and existing ML-based branching rules. Just like existing ML-based branching rules, our approach solves significantly fewer linear programs on average than SCIP’s default branching rule and results in faster solution of the MIPs tested. Compared to the state-of-the-art ML-based branching rule that utilizes a graph neural network (GNN) model, our model does not require a GPU for its deployment and involves fewer than 2% of the number of parameters of the GNN model. Due to its simplicity, our model is much easier to build and utilize in practice. We present extensive computational results on many problem classes to illustrate these findings.

Keywords

Status: accepted

Back to the list of papers