Abstract: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 this https URL.
| Comments: | ICML2026 preprint, camera ready in progress |
| Subjects: | Artificial Intelligence (cs.AI); Optimization and Control (math.OC) |
| Cite as: | arXiv:2605.10401 [cs.AI] |
| (or arXiv:2605.10401v1 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2605.10401 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Zhinan Hou [view email]
[v1]
Mon, 11 May 2026 11:41:54 UTC (387 KB)