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

Computer Science > Machine Learning arXiv:2604.00094 (cs) [Submitted on 31 Mar 2026] Title:Speeding Up Mixed-Integer Programming Solvers with Sparse Learning for Branching Authors:Selin Bayramoğlu, George L Nemhauser, Nikolaos V Sahinidis View a PDF of the paper titled Speeding Up Mixed-Integer Programming Solvers with Sparse Learning for Branching, by Selin Bayramo\u{g}lu and 2 other authors 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...