Evo-B&B: Behavior-Aware LLM-Guided Joint Evolution of Branching and Node Selection Policies for MILP

Jiayu Chen; Chentong Chen; Yuhan Liu; Ye Fan; Jianyong Sun; Jialong Shi

cs.AIOct 16, 2026

Evo-B&B: Behavior-Aware LLM-Guided Joint Evolution of Branching and Node Selection Policies for MILP

Authors: Jiayu Chen, Chentong Chen, Yuhan Liu, Ye Fan, Jianyong Sun, Jialong Shi

Organizations: School of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an, China · School of Electronics and Information, Northwestern Polytechnical University, Xi’an, China

Abstract

In branch-and-bound for Mixed-Integer Linear Programming (MILP), branching and node selection are two critical and tightly coupled decisions, yet most existing learning-based approaches focus on optimizing them separately. We propose Evo-B&B, an LLM-guided evolutionary framework that jointly evolves executable branching and node selection policies using end-to-end SCIP solving feedback. To improve search efficiency and reduce redundant evaluations of behaviorally similar policies, Evo-B&B introduces a behavior-aware multi-island evolutionary mechanism. It measures policy similarity from branching and node-selection behaviors on a fixed set of B&B decision states and uses this similarity to preserve population diversity. We evaluate Evo-B&B on four standard MILP benchmarks across multiple instance scales. Experimental results show that Evo-B&B achieves competitive solving performance and generalizes well to larger-scale instances, while ablation studies further demonstrate the effectiveness of joint evolution and behavior-aware diversity management.

Figures & tables

Figure 1: Overview of the Evo-B&B framework. Evo-B&B jointly evolves branching and node-selection policies through LLM-guided multi-island evolution, behavior-aware population management, and selective parameter optimization.

Setcover:	Easy			Medium			Hard
Method	Time(s) $\downarrow$	Nodes $\downarrow$	Wins $\uparrow$	Time(s) $\downarrow$	Nodes $\downarrow$	Wins $\uparrow$	Time(s) $\downarrow$	Nodes $\downarrow$	Wins $\uparrow$
FSB	31.52	75.80	0/63	457.31	389.31	0/34	3557.49	1610.46	0/2
RPB	8.41	323.05	0/80	113.72	8982.70	0/78	1841.47	132637.61	0/54
Default	8.77	323.05	0/80	115.51	8877.84	0/78	1839.25	131968.26	0/54
GNN	17.13	407.16	0/73	346.66	4318.96	0/44	3487.07	21551.94	0/7
Hybrid	35.00	158.62	0/57	432.05	1213.90	0/39	3445.38	8280.55	0/10

Table 1: Main results on four MILP benchmarks. Lower Time and Nodes are better, while higher Wins is better. Best results are shown in bold.

Setcover:	Easy			Medium
Variant	Time(s) $\downarrow$	Wins $\uparrow$	Nodes $\downarrow$	Time(s) $\downarrow$	Wins $\uparrow$	Nodes $\downarrow$
No similarity	5.15	14/80	544.5	114.10	5/77	12937.6
AST	3.66	13/80	520.5	95.63	8/77	13390.2
Node only	10.37	0/78	299.4	236.01	0/58	4069.4
Branch only	7.98	0/79	494.2	152.91	0/73	7739.6
Independent Node+Branch	9.50	0/78	471.2	242.90	0/58	4322.0

Table 2: Ablation results on Setcover and Indset. Lower Time and Nodes are better, while higher Wins is better. Best results are shown in bold.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Benchmark	Configurations
Set Covering	Easy: 500 rows, 1000 columns, density=0.05 Medium: 1000 rows, 1000 columns, density=0.05 Hard: 2000 rows, 1000 columns, density=0.05
Combinatorial Auctions	Easy: 100 items, 500 bids Medium: 200 items, 1000 bids Hard: 300 items, 1500 bids
Capacitated Facility Location	Easy: 100 customers, 100 facilities, ratio=5 Medium: 200 customers, 100 facilities, ratio=5 Hard: 400 customers, 100 facilities, ratio=5
Maximum Independent Set	Easy: 750 nodes, affinity=4 Medium: 1000 nodes, affinity=4 Hard: 1500 nodes, affinity=4

Appendix

Table 3: Detailed configurations of the MILP benchmark datasets.

Figure 2: Evolution of the joint policy discovered by Evo-B&B on Indset. The curve tracks the global-best score and highlights representative policy updates.

Problem	Iter.	Time (h)	LLM Calls	Input (M)	Output (M)	Total (M)	Solver Calls
Setcover	150/150	9.42	600	3.97	0.87	4.84	11,230
Cauctions	150/150	3.15	600	3.34	0.66	4.00	7,340
Indset	101/150	10.02	404	2.24	0.39	2.64	6,180
Facilities	100/150	10.25	400	2.28	0.46	2.74	5,840
Total	501/600	32.83	2,004	11.83	2.39	14.22	30,590

Appendix

Table 4: Computational cost of Evo-B&B during evolutionary search. Token counts are reported in millions (M), and Solver Calls denote instance-level SCIP evaluations.

Branch and Bound

Branch and bound is an exact search method that uses bounds to prune subproblems and certify optimal solutions.

See all 28 papers

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
BiFE: Search-Efficient Discovery of CPU-Only Branching Policies via LLM-based Bi-Fidelity Evolution
Sep 29, 2026Ce Zhang, Bin Zhang, Zhiwei Xu +5Multi-Fidelity Optimization Automated Algorithm Discovery
Institute of Automation, Chinese Academy of Sciences · School of Artificial Intelligence, University of Chinese Academy of Sciences · Shandong University

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

Branch and Bound

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

BiFE: Search-Efficient Discovery of CPU-Only Branching Policies via LLM-based Bi-Fidelity Evolution