arXiv:2509.04007cs.AI2025-09被引 4

用大模型自动优化局部搜索求解器,提升组合优化效率。

AutoPBO: LLM-powered Optimization for Local Search PBO Solvers

  • 用大语言模型自动设计求解器内部启发式策略。
  • 在四个公开基准上显著优于现有局部搜索方法。
  • 适合想自动化算法设计的优化领域研究者。

伪布尔优化(PBO)通过伪布尔约束为组合问题建模提供强大框架。局部搜索求解器在PBO求解中表现优异,其效率高度依赖于内部启发式策略,但实际设计常需大量专家参与和手动调优。尽管大语言模型(LLMs)在自动化算法设计方面展现出潜力,其在优化PBO求解器中的应用仍属空白。本文提出AutoPBO,一种基于大模型的新型框架,可自动增强局部搜索型PBO求解器。我们在四个公开基准上进行实验,包括一个真实世界基准、来自PB竞赛的基准、整数线性规划优化基准以及一个手工构造的组合优化基准,评估AutoPBO的性能提升,并与六种先进方法对比,涵盖两种局部搜索型PBO求解器NuPBO和OraSLS,两种完整型PBO求解器PBO-IHS和RoundingSat,以及两种混合整数规划(MIP)求解器Gurobi和SCIP。结果表明,AutoPBO在局部搜索方法中实现显著改进,同时保持与最先进方法相当的竞争力,证明其在自动化局部搜索求解器设计方面具有广阔前景。

原文摘要 · Abstract (English)

Pseudo-Boolean Optimization (PBO) provides a powerful framework for modeling combinatorial problems through pseudo-Boolean (PB) constraints. Local search solvers have shown excellent performance in PBO solving, and their efficiency is highly dependent on their internal heuristics to guide the search. Still, their design often requires significant expert effort and manual tuning in practice. While Large Language Models (LLMs) have demonstrated potential in automating algorithm design, their application to optimizing PBO solvers remains unexplored. In this work, we introduce AutoPBO, a novel LLM-powered framework to automatically enhance PBO local search solvers. We conduct experiments on a broad range of four public benchmarks, including one real-world benchmark, a benchmark from PB competition, an integer linear programming optimization benchmark, and a crafted combinatorial benchmark, to evaluate the performance improvement achieved by AutoPBO and compare it with six state-of-the-art competitors, including two local search PBO solvers NuPBO and OraSLS, two complete PB solvers PBO-IHS and RoundingSat, and two mixed integer programming (MIP) solvers Gurobi and SCIP. AutoPBO demonstrates significant improvements over previous local search approaches, while maintaining competitive performance compared to state-of-the-art competitors. The results suggest that AutoPBO offers a promising approach to automating local search solver design.

组合优化大模型局部搜索自动算法设计

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。