LLM4Branch: Large Language Model for Discovering Efficient Branching Policies of Integer Programs
This work addresses the bottleneck of designing branching policies in MILP solvers, offering an automated approach that outperforms existing CPU-based methods.
LLM4Branch uses large language models to automatically discover efficient branching policies for Mixed Integer Linear Programming solvers, achieving state-of-the-art performance among CPU-based methods and competitive results with GPU-based models.
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.