Speeding Up Mixed-Integer Programming Solvers with Sparse Learning for Branching

View PDF

Abstract:Machine learning is increasingly used to improve decisions within branch-and-bound algorithms for mixed-integer programming. Many existing approaches rely on deep learning, which often requires very large training datasets and substantial computational resources for both training and deployment, typically with GPU parallelization. In this work, we take a different path by developing interpretable models that are simple but effective. We focus on approximating strong branching (SB) scores, a highly effective yet computationally expensive branching rule. Using sparse learning methods, we build models with fewer than 4% of the parameters of a state-of-the-art graph neural network (GNN) while achieving competitive accuracy. Relative to SCIP's built-in branching rules and the GNN-based model, our CPU-only models are faster than the default solver and the GPU-accelerated GNN. The models are simple to train and deploy, and they remain effective with small training sets, which makes them practical in low-resource settings. Extensive experiments across diverse problem classes demonstrate the efficiency of this approach.

Comments: 21 pages, 2 figures

Subjects:

Machine Learning (cs.LG); Optimization and Control (math.OC)

Cite as: arXiv:2604.00094 [cs.LG]

(or arXiv:2604.00094v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2604.00094

arXiv-issued DOI via DataCite (pending registration)

Submission history

From: Selin Bayramoğlu [view email] [v1] Tue, 31 Mar 2026 18:17:56 UTC (627 KB)