用大模型自动发现高效分支策略，提升整数规划求解速度。
LLM4Branch: Large Language Model for Discovering Efficient Branching Policies of Integer Programs
- 用大模型生成可执行的分支程序骨架并优化参数
- 在少量实例上通过端到端性能反馈优化，无需专家标注
- 在标准测试集上达到当前基于CPU方法最佳表现
高效的分支策略对加速混合整数线性规划（MILP）求解器至关重要。传统设计依赖人工启发式规则，如今机器学习成为自动化该过程的有力手段。然而，现有学习方法常受限于昂贵的专家示范数据，且训练目标与求解器端到端性能存在差距。本文提出 LLM4Branch，一种利用大语言模型（LLM）自动发现高效分支策略的新框架。具体而言，所发现的策略是一个可执行程序，其程序骨架由 LLM 生成，参数向量通过零阶优化方法在少数实例上基于端到端性能反馈进行优化。在标准 MILP 基准上的大量实验表明，LLM4Branch 在基于 CPU 的方法中建立了新基准，并达到与先进基于 GPU 模型相媲美的性能。代码已开源：https://github.com/hzn18/LLM4Branch。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。