AutoPBO: LLM-powered Optimization for Local Search PBO Solvers

📄 arXiv: 2509.04007v1 📥 PDF

作者: Jinyuan Li, Yi Chu, Yiwen Sun, Mengchuan Zou, Shaowei Cai

分类: cs.AI

发布日期: 2025-09-04

💡 一句话要点

AutoPBO：利用LLM优化局部搜索PBO求解器，提升求解性能

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

关键词: 伪布尔优化 局部搜索 大型语言模型 自动化算法设计 启发式算法 组合优化 PBO求解器

📋 核心要点

  1. 局部搜索PBO求解器依赖专家设计的启发式算法，但人工设计耗时耗力，缺乏自动化手段。
  2. AutoPBO利用LLM自动优化PBO局部搜索求解器，旨在减少人工干预，提升求解性能。
  3. 实验表明，AutoPBO在多个基准测试中显著优于现有局部搜索方法，并与先进求解器具有竞争力。

📝 摘要（中文）

伪布尔优化(PBO)提供了一个强大的框架，通过伪布尔(PB)约束来建模组合问题。局部搜索求解器在PBO求解中表现出卓越的性能，其效率高度依赖于内部启发式算法来指导搜索。然而，这些启发式算法的设计通常需要大量的专家努力和手动调整。虽然大型语言模型(LLM)在自动化算法设计方面显示出潜力，但它们在优化PBO求解器方面的应用仍未被探索。本文介绍AutoPBO，这是一个新颖的LLM驱动的框架，用于自动增强PBO局部搜索求解器。我们在四个公共基准测试上进行了实验，包括一个真实世界的基准测试、一个来自PB竞赛的基准测试、一个整数线性规划优化基准测试和一个精心设计的组合基准测试，以评估AutoPBO实现的性能改进，并将其与六个最先进的竞争对手进行比较，包括两个局部搜索PBO求解器NuPBO和OraSLS，两个完整的PB求解器PBO-IHS和RoundingSat，以及两个混合整数规划(MIP)求解器Gurobi和SCIP。AutoPBO在先前的局部搜索方法上表现出显著的改进，同时与最先进的竞争对手相比保持了具有竞争力的性能。结果表明，AutoPBO为自动化局部搜索求解器设计提供了一种有前景的方法。

🔬 方法详解

问题定义：伪布尔优化(PBO)求解器的性能高度依赖于其内部的启发式算法。然而，设计这些启发式算法通常需要领域专家的深入知识和耗时的手动调整，这限制了PBO求解器的开发效率和可扩展性。现有方法缺乏自动化的启发式算法设计和优化机制。

核心思路：AutoPBO的核心思路是利用大型语言模型(LLM)的强大代码生成和理解能力，自动探索和优化PBO局部搜索求解器的启发式算法。通过将启发式算法的设计过程转化为LLM可以理解和操作的文本形式，AutoPBO能够自动生成、评估和改进启发式算法，从而提升求解器的性能。

技术框架：AutoPBO框架主要包含以下几个模块：1) 提示工程模块：设计合适的提示，引导LLM生成有效的启发式算法代码。2) 代码生成模块：利用LLM根据提示生成候选的启发式算法代码。3) 评估模块：在预定义的基准测试集上评估生成的启发式算法的性能。4) 优化模块：根据评估结果，利用LLM进一步优化启发式算法，迭代提升性能。整个过程形成一个闭环的自动化优化流程。

关键创新：AutoPBO的关键创新在于将LLM引入到PBO求解器的启发式算法设计过程中，实现了启发式算法的自动化生成和优化。与传统的手动设计方法相比，AutoPBO能够更高效地探索更广阔的启发式算法空间，发现更优的解决方案。

关键设计：AutoPBO的关键设计包括：1) 精心设计的提示模板，用于引导LLM生成高质量的启发式算法代码。2) 一种基于性能反馈的优化策略，利用LLM迭代改进启发式算法。3) 一种有效的代码执行和评估机制，确保生成的代码能够正确运行并准确评估其性能。具体的参数设置和网络结构等技术细节在论文中未详细说明，属于未知信息。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

AutoPBO在四个公共基准测试中进行了评估，包括真实世界的基准测试、PB竞赛基准测试、整数线性规划优化基准测试和组合基准测试。实验结果表明，AutoPBO显著优于现有的局部搜索方法，并在某些基准测试中与最先进的完整求解器（如PBO-IHS和RoundingSat）以及混合整数规划求解器（如Gurobi和SCIP）的性能相当甚至更好。具体的性能提升幅度在论文中有所体现，但此处不赘述。

🎯 应用场景

AutoPBO具有广泛的应用前景，可应用于各种组合优化问题，如调度、规划、资源分配等。通过自动化PBO求解器的设计，AutoPBO可以降低开发成本，提高求解效率，从而在工业界和学术界产生重要影响。未来，AutoPBO可以进一步扩展到其他类型的优化问题和求解器，推动自动化算法设计的发展。

📄 摘要（原文）

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.