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.

Many industries, from logistics to energy management, rely on solving complex mathematical problems known as integer programming. Solving these problems efficiently depends on a critical decision-making step called "branching", which helps the computer navigate millions of possible solutions to find the best one. Traditionally, these rules were either manually designed by experts using specialized knowledge or required massive amounts of data and expensive hardware to learn through AI. We introduced LLM4Branch, a framework that uses large language models to automatically discover high-performance branching policies. It proposes new computer programs, tests how well they solve math problems, and iteratively refines them based on actual performance feedback. Surprisingly, this method requires only eight training examples to succeed and produces lightweight policies while performing as well as much heavier AI models