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

Tengfei Liu; Jinrun Liu; Bai Yan; Yuhui Shi; Qi Zhao

cs.LGOct 10, 2026

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

Authors: Tengfei Liu, Jinrun Liu, Bai Yan, Yuhui Shi, Qi Zhao

Organizations: 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

Abstract

Branch-and-bound (BnB) solves mixed-integer linear programs by constructing and exploring a search tree. Node selection and branching are two recurrent decisions that directly determine the tree. Learning-based approaches typically optimize either decision in isolation and condition on a mostly local view, leaving the coupled evolution of the search tree insufficiently modeled. This paper proposes Seq-BnB, a sequence-structured framework that learns branching and node selection from a shared global representation of the evolving BnB process. Seq-BnB serializes node creations, node updates, node-selection events, and branching events into typed tokens, producing a causal event sequence of the search trajectory. A self-attention encoder summarizes this global search history, a bipartite graph neural network encodes the current LP relaxation, and context-conditioned decision heads score branching variables and open nodes. To reduce distribution shift between expert demonstrations and learned policies, Seq-BnB is trained with DAgger-style data aggregation. On four MILP benchmark families, Seq-BnB consistently processes fewer BnB nodes than heuristic and learning-based baselines, with strong solution times on both standard and larger transfer instances. While this paper evaluates Seq-BnB instantiation for branching and node selection, it accommodates additional solver decisions, such as cut selection, by introducing new action tokens and decision heads.

Figures & tables

Figure 1: Architecture of Seq-BnB. The evolving BnB tree and solver actions are serialized into typed tokens and encoded by a self-attention module. Local LP relaxations are encoded by a bipartite GNN, and cross-attention conditions branching and node-selection decisions on the global search context.

Method	Set Covering		Comb. Auction		Facility Location		Max Ind. Set
Method	Time	Nodes	Time	Nodes	Time	Nodes	Time	Nodes
SB+Oracle	9.01	20.89	59.34	183.28	82.99	131.58	101.37	30.44
PSB+Estimate	3.73	37.25	10.98	886.54	41.33	226.81	9.88	101.93
RankNet+PSB	3.87	37.49	16.52	1247.04	28.70	256.24	11.42	86.91
L2C+PSB	3.60	38.86	29.75	1806.76	30.80	265.38	7.78	156.95
L2B+Estimate	2.99	32.06	10.13	292.23	28.60	180.19	6.45	38.10

Table 1: Standard test results (100 instances per family).

Method	Set Covering		Comb. Auction		Facility Location		Max Ind. Set
Method	Time	Nodes	Time	Nodes	Time	Nodes	Time	Nodes
SB+Oracle	121.58	234.79	3363.43	2074.32	2304.62	207.62	2795.54	183.65
PSB+Estimate	25.66	667.39	2174.09	21105.59	748.19	1390.19	1217.84	13517.28
RankNet+PSB	40.38	802.18	1228.58	37844.01	2113.60	4398.48	644.66	11997.45
L2C+PSB	45.72	696.74	1526.97	66897.30	1407.08	3611.90	601.47	16559.32
L2B+Estimate	28.97	462.74	618.79	11771.63	747.34	1475.62	459.58	6085.88

Table 2: Results on larger transfer instances (100 instances per family).

Method	Set Covering		Comb. Auction		Facility Location		Max Ind. Set
Method	Time	Nodes	Time	Nodes	Time	Nodes	Time	Nodes
w/o Seq (branch head)	3.51	31.94	11.83	281.63	41.56	238.42	7.48	42.73
BR-only	3.04	34.24	12.18	306.54	39.56	225.63	6.92	39.84
NS-only	3.80	32.25	27.47	684.73	40.88	236.94	7.89	68.74
w/o DAgger	5.36	43.21	18.21	397.63	49.37	374.35	8.64	49.51
Seq-BnB	2.81	28.62	10.61	252.34	30.22	164.16	6.35	36.54

Table 3: Core ablations on standard test instances (Time/Nodes).

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Token or Quantity	Feature Group	Availability	Use in Scoring
Open-node token	Stored node bound $\ell(u)$ , estimate $c(u)$ , depth $d(u)$ , creation/visit order $s(u)$ , and currently available global statistics	Available before node selection from the solver’s open-node data structure; no LP relaxation is solved solely for scoring open nodes	Scores node selection through Eq. equation 13
Processed-node update	Visited, fathomed, and incumbent-update indicators, together with realized node status	Available only after the corresponding node has been processed or fathomed, or after an incumbent update has occurred	Past context only
Node-selection action token	Selected-node statistics $d(n_{t})$ , $\ell(n_{t})$ , $c(n_{t})$ , and the local summary $\mathbf{s}^{\mathrm{node}}(n_{t})$ after the selected node is processed	Created after the node-selection decision; $\mathbf{s}^{\mathrm{node}}(n_{t})$ is not available before selecting $n_{t}$	Not used to choose $n_{t}$ ; used only for branching at the processed node and future decisions
Branching candidates	Local variable embeddings $\mathbf{h}^{\mathrm{var}}_{j}(n_{t})$ for fractional candidate variables	Available after solving the LP relaxation at the selected node $n_{t}$	Scores branching through Eqs. equation 11 and equation 12
Branching action token	Selected-variable embedding $\mathbf{h}^{\mathrm{var}}_{j_{t}}(n_{t})$ and current search statistics	Created after the branching variable has been selected	Future context only

Appendix

Table 4: Information availability in the online construction of Seq-BnB.

Statistic	Set Covering		Comb. Auction		Facility Location		Max Ind. Set
Statistic	Test	Transfer	Test	Transfer	Test	Transfer	Test	Transfer
Avg. binary variables	1000.00	1000.00	500.00	1000.00	100.00	200.00	500.00	1000.00
Avg. integer variables	0.00	0.00	0.00	0.00	0.00	0.00	0.00	0.00
Avg. continuous variables	0.00	0.00	0.00	0.00	10000.00	40000.00	0.00	0.00
Avg. constraints	500.00	1000.00	191.90	386.10	10201.00	40401.00	2088.60	4219.30
Instances	100	100	100	100	100	100	100	100

Appendix

Table 5: Problem instance statistics for test and transfer sets.

Method	Set Covering			Comb. Auction			Facility Location			Max Ind. Set
Method	Time	Nodes	Wins	Time	Nodes	Wins	Time	Nodes	Wins	Time	Nodes	Wins
SB+Oracle	9.01	20.89	–	59.34	183.28	–	82.99	131.58	–	101.37	30.44	–
PSB+Estimate	3.73	37.25	8	10.98	886.54	9	41.33	226.81	1	9.88	101.93	6
RankNet+PSB	3.87	37.49	12	16.52	1247.04	1	28.70	256.24	28	11.42	86.91	4
L2C+PSB	3.60	38.86	12	29.75	1806.76	0	30.80	265.38	21	7.78	156.95	15
L2B+Estimate	2.99	32.06	24	10.13	292.23	49	28.60	180.19	30	6.45	38.10	27

Appendix

Table 6: Results on standard test instances.

Method	Set Covering			Comb. Auction			Facility Location			Max Ind. Set
Method	Time	Nodes	Wins	Time	Nodes	Wins	Time	Nodes	Wins	Time	Nodes	Wins
SB+Oracle	121.58	234.79	–	3363.43	2074.32	–	2304.62	207.62	–	2795.54	183.65	–
PSB+Estimate	25.66	667.39	43	2174.09	21105.59	0	748.19	1390.19	14	1217.84	13517.28	1
RankNet+PSB	40.38	802.18	1	1228.58	37844.01	1	2113.60	4398.48	0	644.66	11997.45	4
L2C+PSB	45.72	696.74	2	1526.97	66897.30	0	1407.08	3611.90	0	601.47	16559.32	5
L2B+Estimate	28.97	462.74	31	618.79	11771.63	72	747.34	1475.62	16	459.58	6085.88	17

Appendix

Table 7: Results on transfer instances.

Method	Set Covering			Comb. Auction			Facility Location			Max Ind. Set
Method	Time	Nodes	Wins	Time	Nodes	Wins	Time	Nodes	Wins	Time	Nodes	Wins
Seq-BnB (w/o Seq)	3.51	31.94	18	11.83	281.63	21	41.56	238.42	15	7.48	42.73	7
Seq-BnB	2.81	28.62	82	10.61	252.34	79	30.22	164.16	85	6.35	36.54	93

Appendix

Table 8: Effect of sequence context on standard test instances.

Figure 2: Branching imitation accuracy with and without sequence context. ACC@

k

measures whether the expert variable is among the top

k

predicted candidates. Sequence context improves top-

k

accuracy on most benchmarks; together with Table 8 , this suggests that modest gains in single-step imitation can translate into larger improvements over the subsequent BnB search.

Method	Set Covering			Comb. Auction			Facility Location			Max Ind. Set
Method	Time	Nodes	Wins	Time	Nodes	Wins	Time	Nodes	Wins	Time	Nodes	Wins
Seq-BnB (BR-only)	3.04	34.24	12	12.18	306.54	11	39.56	225.63	3	6.92	39.84	15
Seq-BnB (NS-only)	3.80	32.25	6	27.47	684.73	3	40.88	236.94	5	7.89	68.74	10
Seq-BnB	2.81	28.62	82	10.61	252.34	86	30.22	164.16	92	6.35	36.54	75

Appendix

Table 9: Joint learning ablation

Method	Set Covering			Comb. Auction			Facility Location			Max Ind. Set
Method	Time	Nodes	Wins	Time	Nodes	Wins	Time	Nodes	Wins	Time	Nodes	Wins
Seq-BnB (w/o DAgger)	5.36	43.21	5	18.21	397.63	0	49.37	374.35	2	8.64	49.51	4
Seq-BnB	2.81	28.62	95	10.61	252.34	100	30.22	164.16	98	6.35	36.54	96

Appendix

Table 10: Effect of DAgger data aggregation.

$L_{\max}$	Set Covering			Comb. Auction			Facility Location			Max Ind. Set
$L_{\max}$	Time	Nodes	Wins	Time	Nodes	Wins	Time	Nodes	Wins	Time	Nodes	Wins
100	3.46	34.87	5	13.28	334.52	1	39.84	232.65	0	7.58	45.37	0
300	3.07	31.46	8	11.76	287.91	4	34.92	193.74	6	6.91	39.82	2
500	2.81	28.62	87	10.61	252.34	95	30.22	164.16	94	6.35	36.54	98

Appendix

Table 11: Effect of maximum sequence-window length

L_{\max}

on standard test instances.

$\lambda$	Set Covering			Comb. Auction			Facility Location			Max Ind. Set
$\lambda$	Time	Nodes	Wins	Time	Nodes	Wins	Time	Nodes	Wins	Time	Nodes	Wins
0.01	3.23	32.84	17	11.42	294.18	22	35.76	206.43	18	6.84	40.43	22
0.05	2.96	30.15	24	10.97	265.83	27	31.48	178.92	27	6.57	37.88	28
0.1	2.81	28.62	35	10.61	252.34	33	30.22	164.16	34	6.35	36.54	34
0.5	3.18	31.76	16	12.64	321.57	12	33.95	191.35	14	7.12	43.16	11
1.0	3.59	35.02	8	14.28	402.91	6	37.64	224.78	7	7.64	51.28	5

Appendix

Table 12: Effect of joint-loss weight

\lambda

on standard test instances.

Explore similar work

May 11, 2026

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

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.

Zhinan Hou, Xingchen Li, Yankai Zhang +2

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

Ask PDF

Mar 31, 2026

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

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.

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

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

Learning to Optimize Branch and Bound Mixed-Integer Linear Programming

Ask PDF

Jan 8, 2026

A General Neural Backbone for Mixed-Integer Linear Optimization via Dual Attention

Mixed-integer linear programming (MILP) is a foundational framework for combinatorial optimization across science and engineering, but remains hard to solve at scale due to NP-hardness. Recent learning-based methods typically model MILP instances as variable-constraint bipartite graphs and use Graph Neural Networks (GNNs) for representation learning, yet their locality limits representation power. We propose an attention-driven neural backbone that adopts an element-centric view of variables and constraints, with dual attention performing parallel intra-type self-attention and inter-type cross-attention. Across three representative tasks at the instance, element, and solving-state levels, our model consistently outperforms conventional GNN-based architectures, highlighting attention-based, element-centric modeling as a powerful foundation for learning-enhanced combinatorial optimization.

Peixin Huang, Yaoxin Wu, Yining Ma +3

Shenzhen Research Institute, Shandong University, China

Graph Neural Networks Mixed-Integer Linear Programming Linear Programming Neural Combinatorial Optimization Integer Linear Programming

Ask PDF