LLM4Branch：用大语言模型发现整数规划的高效分支策略

高效的分支策略对于加速混合整数线性规划（MILP）求解器至关重要。其设计长期依赖手工启发式，如今机器学习已成为自动化这一过程的有前景范式。然而，现有基于学习的方法常受制于对昂贵专家示范的依赖，以及训练目标与求解器端到端性能之间的差距。在本工作中，我们提出LLM4Branch，一个利用大语言模型（LLM）自动化发现高效分支策略的新框架。具体而言，发现的策略是一个可执行程序，由LLM生成的程序骨架和一个参数向量构成，参数向量借助少量实例的端到端性能反馈通过零阶方法进行优化。在标准MILP基准上的大量实验表明，LLM4Branch在基于CPU的方法中确立了新的最优水平，并取得与先进GPU模型相当的性能。代码发布于 https://github.com/hzn18/LLM4Branch。