Efficient cpu-only search finds fast branching rules for optimization
BiFE: Search-Efficient Discovery of CPU-Only Branching Policies via LLM-based Bi-Fidelity Evolution
Artificial Intelligence
Summary
Solving certain math problems called mixed-integer linear programs depends a lot on picking the right variable to split on, called branching. The authors show that using code created by large language models can help design smart decision rules for branching that run fast on regular CPUs. They introduced a way to quickly test many possible rules by first filtering with cheap estimates and only fully testing the best ones. This approach found new rules that are faster than standard methods and even beat some GPU-based AI methods.
What this means in practice
- •For optimization software developers: Use the bi-fidelity evolutionary framework to create fast cpu-only branching rules improving solver efficiency.
- •For operations research engineers: Deploy new lightweight branching policies to speed up mixed-integer linear programming on standard computer hardware.
Authors
Ce Zhang, Bin Zhang, Zhiwei Xu, Hao Chen, Xinyue Lu, Shanwei Fan, Yingxuan Teng, Guoliang Fan
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.