# LLM4Branch: Large Language Model for Discovering Efficient Branching Policies of Integer Programs

arXiv: https://arxiv.org/abs/2605.10401 · HTML: https://mlsanity.com/paper/2605.10401/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 37 references that are in the map.
- First posted on arXiv 11 May 2026.

## Builds on (most cited first, 18 of 18)

- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://mlsanity.com/paper/2506.13131/) (2025)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [LLM-SR: Scientific Equation Discovery via Programming with Large Language Models](https://mlsanity.com/paper/2404.18400/) (2024)
- [Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design](https://mlsanity.com/paper/2501.08603/) (2025)
- [Hybrid Models for Learning to Branch](https://mlsanity.com/paper/2006.15212/) (2020)
- [HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs](https://mlsanity.com/paper/2412.14995/) (2024)
- [Ecole: A Gym-like Library for Machine Learning in Combinatorial Optimization Solvers](https://mlsanity.com/paper/2011.06069/) (2020)
- [The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights](https://mlsanity.com/paper/2203.02433/) (2022)
- [Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm](https://mlsanity.com/paper/2005.10026/) (2020)
- [Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories](https://mlsanity.com/paper/2205.14345/) (2022)
- [A Theoretical and Computational Analysis of Full Strong-Branching](https://mlsanity.com/paper/2110.10754/) (2021)
- [SORREL: Suboptimal-Demonstration-Guided Reinforcement Learning for Learning to Branch](https://mlsanity.com/paper/2412.15534/) (2024)
- [EvoCut: Strengthening Integer Programs via Evolution-Guided Language Models](https://mlsanity.com/paper/2508.11850/) (2025)
- [DHEvo: Data-Algorithm Based Heuristic Evolution for Generalizable MILP Solving](https://mlsanity.com/paper/2507.15615/) (2025)
- [Joint Routing and Charging Problem of Multiple Electric Vehicles: A Fast Optimization Algorithm](https://mlsanity.com/paper/2105.05711/) (2021)

## Built on by (most cited first, 4 of 4)

- [LLM-Guided Evolutionary Search for Constraint Model Reformulation to Improve Solver Efficiency](https://mlsanity.com/paper/2607.28268/) (2026)
- [FormuEvo: LLM-Guided Evolution for Discovering Solver-Efficient Mixed-Integer Programming Formulations](https://mlsanity.com/paper/2608.23353/) (2026)
- [SHSP: Structure-Aware Hierarchical Solution Prediction for Mixed-Integer Linear Programming](https://mlsanity.com/paper/2608.25282/) (2026)
- [BiFE: Search-Efficient Discovery of CPU-Only Branching Policies via LLM-based Bi-Fidelity Evolution](https://mlsanity.com/paper/2609.36735/) (2026)

## Abstract (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.