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

📄 arXiv: 2605.10401v1 📥 PDF

作者: Zhinan Hou, Xingchen Li, Yankai Zhang, Tianxun Li, Keyou You

分类: cs.AI, math.OC

发布日期: 2026-05-11

备注: ICML2026 preprint, camera ready in progress

🔗 代码/项目: GITHUB

💡 一句话要点

提出LLM4Branch框架，利用大语言模型自动化发现高效的混合整数线性规划分支策略。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 混合整数线性规划 大语言模型 分支策略 零阶优化 组合优化 自动化算法设计

📋 核心要点

  1. 现有分支策略依赖人工启发式规则，且基于学习的方法存在对专家数据依赖过重及训练目标与求解器性能不一致的问题。
  2. 提出LLM4Branch框架，利用LLM生成可执行的分支策略程序骨架，并结合零阶优化算法根据端到端性能反馈调整参数。
  3. 实验表明该方法在标准MILP基准测试中刷新了CPU端方法的性能记录，并具备与GPU加速模型相媲美的竞争力。

📝 摘要（中文）

高效的分支策略对于加速混合整数线性规划（MILP）求解器至关重要。传统设计长期依赖人工启发式规则，而机器学习已成为自动化该过程的有前景范式。然而，现有的基于学习的方法常受限于对昂贵专家演示数据的依赖，以及训练目标与求解器端到端性能之间的鸿沟。本文提出了LLM4Branch，这是一个利用大语言模型（LLM）自动化发现高效分支策略的新框架。该框架生成的策略表现为一段可执行程序，包含由LLM生成的程序骨架及一组参数向量。这些参数通过零阶优化方法，在少量实例的端到端性能反馈下进行迭代优化。在标准MILP基准测试上的广泛实验表明，LLM4Branch在基于CPU的方法中达到了新的SOTA水平，并展现出与先进GPU模型相竞争的性能。

🔬 方法详解

问题定义：MILP求解器的核心在于分支策略，旨在通过高效的分支变量选择减少搜索空间。现有方法要么依赖人工设计的启发式规则，要么依赖监督学习（模仿专家行为），这导致了训练目标与求解器最终求解效率之间的偏差，且获取高质量专家数据成本高昂。

核心思路：将分支策略视为一个可执行的程序，利用LLM强大的代码生成能力构建策略骨架，并通过零阶优化（Zeroth-order Optimization）直接针对求解器的端到端性能（如求解时间或节点数）进行参数调优，从而绕过对专家数据的依赖。

技术框架：框架包含两个主要阶段：首先，LLM根据任务描述生成分支策略的程序骨架；其次，通过零阶优化算法（如进化策略或随机搜索）在少量MILP实例上对程序中的参数向量进行迭代更新，以最大化求解器的端到端性能反馈。

关键创新：创新性地将LLM的逻辑推理能力与零阶优化相结合，实现了从“模仿专家”到“直接优化求解性能”的范式转变，有效解决了训练目标与实际求解效率不匹配的难题。

关键设计：采用程序化策略表示，将分支逻辑解耦为结构化的代码骨架与可调参数；利用零阶优化方法，仅需黑盒性能反馈即可更新参数，避免了对求解器内部梯度信息的依赖，增强了方法的通用性与鲁棒性。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

LLM4Branch在标准MILP基准测试中表现卓越，不仅在所有基于CPU的自动化分支策略方法中确立了新的SOTA地位，其性能表现还成功追平了依赖高性能GPU加速的复杂深度学习模型，证明了该方法在计算效率与策略质量上的双重优势。

🎯 应用场景

该研究主要应用于工业级运筹优化领域，如物流调度、生产计划、能源管理及金融投资组合优化等。通过提升MILP求解器的分支效率，该方法能显著缩短复杂组合优化问题的求解时间，在资源受限的工业场景中具有极高的实用价值和推广潜力。

📄 摘要（原文）

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.