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

Selin Bayramoğlu; George L Nemhauser; Nikolaos V Sahinidis

cs.LGMar 31, 2026

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

Authors: Selin Bayramoğlu, George L Nemhauser, Nikolaos V Sahinidis

Organizations: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology · School of Chemical & Biomolecular Engineering, Georgia Institute of Technology

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.

Figures & tables

Figure 1: A common ML pipeline used in previous studies (top path) and our approach (bottom path) for learning to branch.

Data	SC	CA	FL	IS
GNN data	7617 (100K)	11472 (100K)	6193 (100K)	5429 (100K)
LS - Small	1974 (2950)	3030 (3981)	5711 (54721)	478 (582)
SS - Small	30 (300)	47 (399)	39 (5572)	6 (57)
SS - Medium	9 (244)	9 (223)	24 (5184)	5 (30)
SS - Large	6 (191)	6 (157)	27 (4422)	5 (21)

Table 1: Data collection statistics for training datasets with different sampling schemes. The first entry is the average number of instances solved and the second entry is the average number of subproblems solved to generate the dataset.

Model	SC	CA	FL	IS
QL	1630	1708	2043	1282
QS	533	633	620	297
GNN	64,000	64,000	64,000	64,000

Table 2: Average model sizes for the four problem domains. All models are built using training data from small problems.

Model	SC	CA	FL	IS
QL	57.8	57.6	70.1	49.0
QS	57.1	56.9	68.0	46.0
GNN	62.4	58.5	72.4	54.8

Table 3: Accuracy of the models on the SB test set (%).

Table 4: Performance of branching rules on the evaluation instances.

Table 5: Parametric analysis of the quadratic models.

Table 6: Performance of branching rules with quadratic and linear features.

Figure 2: Heat map of features with largest absolute coefficients in QL-500 models.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Feature	Source	Count	Description
Objective coefficient	K	3	Value of the coefficient (raw, positive only, negative only)
Number of constraints	K	1	The number of constraints in which the candidate appears
Statistics for constraint degrees	K	4	The mean, std. dev., min., and max. of the constraint degrees (the number of variables with nonzero coefficients)
Statistics for positive (negative) constraint coefficients	K	10	The count, mean, std. dev., min., and max. of the candidate’s positive (negative) coefficients in the constraints, normalized
Integrality violation	K	1	$\min(\hat{x}_{j}-\lfloor\hat{x}_{j}\rfloor,\lceil\hat{x}_{j}\rceil-\hat{x}_{j})$
Ceiling distance	K	1	$\lceil\hat{x}_{j}\rceil-\hat{x}_{j}$

Appendix

Table 7: Features used for building sparse models

Explore similar work

LLM4Branch: Large Language Model for Discovering Efficient Branching Policies of Integer Programs
May 11, 2026Zhinan Hou, Xingchen Li, Yankai Zhang +2Branch and Bound Mixed-Integer Linear Programming
Department of Automation, BNRist, Tsinghua University, Beijing, China.
Sequence-Structured Decision Learning for Branch-and-Bound in Mixed-Integer Linear Programming
Oct 10, 2026Tengfei Liu, Jinrun Liu, Bai Yan +2Branch and Bound Mixed-Integer Linear Programming
Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen, China · School of Computer Science and Technology, Dongguan University of Technology, Dongguan, China
Optimizing Sparse Boolean Rule Networks using Mixed Integer Linear Programming
Oct 14, 2026Thomas Pammer, Johannes Fürnkranz, Markus SinnlBoolean Function Learning Interpretable ML
Institute for Application-Oriented Knowledge Processing (FAW), Johannes Kepler University Linz, Austria · LIT AI Lab, Johannes Kepler University Linz, Austria · Institute of Business Analytics & Technology Transformation/JKU Business School, Johannes Kepler University Linz, Austria

May 11, 2026J/K move · Enter open · S save

LLM4Branch: Large Language Model for Discovering Efficient Branching Policies of Integer Programs

Zhinan Hou, Xingchen Li, Yankai Zhang, Tianxun Li+1

Department of Automation, BNRist, Tsinghua University, Beijing, China.

Branch and Bound Mixed-Integer Linear Programming Large Language Model-Guided Optimization Learning to Optimize LLM-Based Program Synthesis Integer Linear Programming

Open paper AskPDF arXiv

Efficient branching policies are essential for accelerating Mixed Integer Linear Programming (MILP) solvers. Their design has long relied on hand-crafted heuristics, and now machine learning has emerged as a promising paradigm to automate this process. However, existing learning-based methods are often hindered by their dependence on expensive expert demonstrations and the gap between training objectives and the solver's end-to-end performance. In this work, we propose LLM4Branch, a novel framework that leverages Large Language Models (LLMs) to automate the discovery of efficient branching policies. Specifically, the discovered policy is an executable program with a program skeleton generated by the LLM and a parameter vector, which is optimized via a zeroth-order method over a few instances with their end-to-end performance feedback. Extensive experiments on standard MILP benchmarks demonstrate that LLM4Branch establishes a new state-of-the-art among CPU-based methods and achieves performance competitive with advanced GPU-based models. Codes are available at https://github.com/hzn18/LLM4Branch.

Abstract

Explore similar work

LLM4Branch: Large Language Model for Discovering Efficient Branching Policies of Integer Programs

Sequence-Structured Decision Learning for Branch-and-Bound in Mixed-Integer Linear Programming

Optimizing Sparse Boolean Rule Networks using Mixed Integer Linear Programming