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

Ce Zhang; Bin Zhang; Zhiwei Xu; Hao Chen; Xinyue Lu; Shanwei Fan; Yingxuan Teng; Guoliang Fan

cs.AISep 29, 2026

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

Authors: Ce Zhang, Bin Zhang, Zhiwei Xu, Hao Chen, Xinyue Lu, Shanwei Fan, Yingxuan Teng, Guoliang Fan

Organizations: Institute of Automation, Chinese Academy of Sciences · School of Artificial Intelligence, University of Chinese Academy of Sciences · Shandong University

Abstract

In branch-and-bound (B&B) for mixed-integer linear programming (MILP), branching variable selection critically impacts efficiency. Existing neural branching policies often require GPU inference, while CPU-efficient symbolic expressions lack the representational capacity for complex logic. Large Language Model (LLM)-generated code provides a flexible search space for designing lightweight branching rules with diverse algorithmic logic. To discover effective rules within LLM-based evolutionary frameworks, a core challenge arises: full B&B evaluation on real instances is prohibitively expensive, whereas offline imitation learning suffers from distribution shift. To address this, we introduce a Bi-Fidelity Evolutionary framework (BiFE). It employs low-fidelity imitation scores as a rapid pre-screener and selectively applies high-fidelity on-instance evaluation only to elite candidates, effectively balancing search efficiency with performance reliability. Experiments validate both the search efficiency of BiFE and the competitiveness of its discovered rules, which outperform the SCIP solver and other baselines on CPUs, and even surpass certain GPU-based neural policies.

Figures & tables

Figure 1: The overall framework of BiFE. To balance search efficiency and rule quality, $F_{HF}$ evaluates heuristics via expensive MILP solving while $F_{LF}$ offers a cheap surrogate by measuring consistency with strong-branching decisions. An LLM generator produces new heuristics through three operations: initialization, crossover, and mutation. The evolutionary process has two stages: (1) Initialization: the LLM generates an initial population, ranked by $F_{LF}$ with the top $\alpha$ forming the elite set $\mathcal{E}$ for $F_{HF}$ evaluation. (2) Evolutionary Loop: parent selection is elite-prioritized, where elites are ranked by $F_{HF}$ and others by $F_{LF}$ , and selected parents are passed to the LLM for crossover or mutation. New candidates with $F_{LF}$ exceeding threshold $\tau$ undergo $F_{HF}$ evaluation and are admitted into $\mathcal{E}$ . Survival selection retains all elites and fills the remaining slots from the general population. This selective allocation lets BiFE explore broadly with $F_{LF}$ while using $F_{HF}$ to correct the surrogate on promising candidates.

Figure 2: LLM-based rule generator. Given an operation instruction (initialization, crossover, or mutation), a problem description, and a rule template, the LLM generates a new rule. The LLM-generated rules undergo evolution and selection within the BiFE framework to yield an optimal rule.

Method	CA		SC		MIS		CFL
	Nodes	Time	Nodes	Time	Nodes	Time	Nodes	Time
RPB	$8.79\mathopen{(}3.97\mathclose{)}$	$2.31\mathopen{(}1.60\mathclose{)}$	$24.93\mathopen{(}8.88\mathclose{)}$	$6.13\mathopen{(}1.75\mathclose{)}$	$30.71\mathopen{(}9.47\mathclose{)}$	$8.74\mathopen{(}1.72\mathclose{)}$	$65.51\mathopen{(}5.64\mathclose{)}$	$33.70\mathopen{(}2.07\mathclose{)}$
FiLM	$57.68\mathopen{(}2.93\mathclose{)}$	$2.01\mathopen{(}1.47\mathclose{)}$	$87.23\mathopen{(}4.00\mathclose{)}$	$5.20\mathopen{(}1.68\mathclose{)}$	$108.52\mathopen{(}10.57\mathclose{)}$	$13.78\mathopen{(}2.48\mathclose{)}$	$228.93\mathopen{(}3.17\mathclose{)}$	$30.82\mathopen{(}2.29\mathclose{)}$
Symb4CO	$63.10\mathopen{(}3.06\mathclose{)}$	$1.59\mathopen{(}1.48\mathclose{)}$	$114.74\mathopen{(}4.37\mathclose{)}$	$4.93\mathopen{(}1.76\mathclose{)}$	$70.00\mathopen{(}7.07\mathclose{)}$	$6.35\mathopen{(}1.66\mathclose{)}$	$264.45\mathopen{(}3.12\mathclose{)}$	$33.19\mathopen{(}2.44\mathclose{)}$
GS4CO	$59.66\mathopen{(}3.03\mathclose{)}$	$1.93\mathopen{(}1.43\mathclose{)}$	$112.26\mathopen{(}4.34\mathclose{)}$	$5.21\mathopen{(}1.70\mathclose{)}$	$146.25\mathopen{(}10.29\mathclose{)}$	$8.66\mathopen{(}2.03\mathclose{)}$	$273.15\mathopen{(}3.01\mathclose{)}$	$40.22\mathopen{(}2.36\mathclose{)}$
GNN	$59.41\mathopen{(}3.09\mathclose{)}$	$3.65\mathopen{(}1.99\mathclose{)}$	$92.33\mathopen{(}3.66\mathclose{)}$	$32.36\mathopen{(}3.24\mathclose{)}$	$51.74\mathopen{(}6.16\mathclose{)}$	$9.67\mathopen{(}2.27\mathclose{)}$	$217.83\mathopen{(}3.03\mathclose{)}$	$70.79\mathopen{(}2.64\mathclose{)}$

Table 1: The experimental results on standard benchmarks. Values are reported as geometric mean (geometric standard deviation) over 100 solving attempts per method. Bold font marks the best time among CPU-evaluated methods (our core focus), underline marks cases where the best CPU method additionally outperforms all GPU-evaluated methods. Nodes are reported for completeness but not the primary evaluation metric, and

\star

in the Nodes column marks cases that hit the 1000s time limit.

Method	BIP		OTS		NNV
	PDI	Gap	Nodes	Time	Nodes	Time
RPB	$81057.56\mathopen{(}1.24\mathclose{)}$	$93.47\mathopen{(}13.99\mathclose{)}$	$939.91\mathopen{(}9.01\mathclose{)}$	$320.62\mathopen{(}2.60\mathclose{)}$	$372.96\mathopen{(}31.85\mathclose{)}$	$22.96\mathopen{(}7.85\mathclose{)}$
Symb4CO	$89220.25\mathopen{(}1.07\mathclose{)}$	$132.48\mathopen{(}11.95\mathclose{)}$	$1474.2^{\star}\mathopen{(}3.17\mathclose{)}$	$544.89\mathopen{(}1.94\mathclose{)}$	$365.89\mathopen{(}60.40\mathclose{)}$	$25.43\mathopen{(}15.50\mathclose{)}$
GS4CO	$87270.12\mathopen{(}1.12\mathclose{)}$	$118.91\mathopen{(}12.09\mathclose{)}$	$2107.4^{\star}\mathopen{(}2.11\mathclose{)}$	$961.48\mathopen{(}1.16\mathclose{)}$	$502.99\mathopen{(}80.20\mathclose{)}$	$25.55\mathopen{(}18.31\mathclose{)}$
GNN	$87835.06\mathopen{(}1.08\mathclose{)}$	$88.39\mathopen{(}6.29\mathclose{)}$	$269.80^{\star}\mathopen{(}2.96\mathclose{)}$	$479.07\mathopen{(}2.42\mathclose{)}$	$254.01^{\star}\mathopen{(}18.54\mathclose{)}$	$58.55\mathopen{(}11.49\mathclose{)}$
LLM4Branch	$\textbf{\lx@text@underline{76010.83}}\mathopen{(}1.30\mathclose{)}$	$72.25\mathopen{(}14.12\mathclose{)}$	$4709.2^{\star}\mathopen{(}2.29\mathclose{)}$	$785.75\mathopen{(}1.51\mathclose{)}$	$362.27\mathopen{(}23.67\mathclose{)}$	$18.32\mathopen{(}4.49\mathclose{)}$

Table 2: Experimental results on real-world benchmarks. Similarly, values are reported as geometric mean (geometric standard deviation) over 100 solving attempts per method. Bold marks the best gap/PDI/time among CPU methods, underline indicates the best CPU method outperforms all GPU methods.

\star

indicates hitting the 1000s time limit.

Method	SC	CA	CFL	MIS
BiFE w/o $F_{LF}$	4.66	1.52	29.38	6.54
BiFE	4.58	1.51	28.29	6.26

Table 3: Times of rules designed by BiFE and BiFE w/o

F_{LF}

on the test instances of standard benchmarks.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Benchmarks	Parameters	Test	Transfer
Set Covering	Items Sets	500 1000	1000 1000
Combinatorial Auctions	Items Bids	100 500	200 1000
Maximum Independent Set	Nodes Affinity	500 4	1000 4
Capacitated Facility Location	Customers Facilities	100 100	200 100

Appendix

Table 4: Size of the test and transfer instances in standard benchmarks

Method	CA		SC		MIS		CFL
	Nodes	Time	Nodes	Time	Nodes	Time	Nodes	Time
BiFE	$70.50\mathord{\pm}3.11$	$1.51\mathord{\pm}1.41$	$109.17\mathord{\pm}4.10$	$4.58\mathord{\pm}1.67$	$81.75\mathord{\pm}7.75$	$6.26\mathord{\pm}1.62$	$266.52\mathord{\pm}2.99$	$28.29\mathord{\pm}2.22$
STRCMP	$8.88\mathord{\pm}3.77$	$2.69\mathord{\pm}1.52$	$23.06\mathord{\pm}8.46$	$7.20\mathord{\pm}1.73$	$25.93\mathord{\pm}9.76$	$4.81\mathord{\pm}2.03$	$70.86\mathord{\pm}5.77$	$32.61\mathord{\pm}2.03$

Appendix

Table 5: Comparison between BiFE and STRCMP on standard benchmarks.

Parameter	Value
Population size	8
Initial population size	16
Number of instances in $F_{HF}$	20
Random seed per $F_{HF}$ instance	0
Maximum sampled heuristics (LLM calls)	100
LLM output time limit (s)	60

Appendix

Table 6: Hyperparameter settings of the evolutionary algorithm.

Setting	Holm-adjusted $p$	BiFE win/tie/loss
CA Test	0.4128	12/0/8
SC Test	0.6146	15/0/5
MIS Test	0.9354	12/0/8
CFL Test	0.0018	18/0/2
CA Transfer	0.0499	17/0/3
SC Transfer	1.0000	10/0/10

Appendix

Table 7: Exact two-sided Wilcoxon signed-rank tests comparing instance-level solving time of BiFE and LLM4Branch. Each test uses 20 instance-level geometric means, obtained by aggregating five seeds per instance. Values are Holm-adjusted

p

-values across all eight comparisons; bold values are below 0.05.

Explore similar work

LLM4Branch: Large Language Model for Discovering Efficient Branching Policies of Integer Programs
May 11, 2026Zhinan Hou, Xingchen Li, Yankai Zhang +2Mixed-Integer Programming Large Language Model Policy Optimization
Department of Automation, BNRist, Tsinghua University, Beijing, China.
Compute Allocation in Evolutionary Search: From Depth-Breadth to Multi-Armed Bandits
May 28, 2026Sixue Xing, Haoyu He, Kerui Wu +4Evolutionary Search Bandits
University of Notre Dame · 2Northeastern University · University of Massachusetts Amherst +4
MicroEvo: Knowledge-Guided LLM Sampling for Efficient Microarchitecture Design Space Exploration
Aug 6, 2026Jia Xiong, Runkai Li, Chenxu Niu +11Evolutionary Search Neural Architecture Search
Southeast University · National Center of Technology Innovation for EDA · NVIDIA Corporation +4

May 11, 2026, cs.AIJ/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.

Mixed-Integer Programming Large Language Model Policy Optimization Openai

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

Compute Allocation in Evolutionary Search: From Depth-Breadth to Multi-Armed Bandits

MicroEvo: Knowledge-Guided LLM Sampling for Efficient Microarchitecture Design Space Exploration