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)

关键词: 伪布尔优化 局部搜索 大型语言模型 算法优化 自动化设计

📋 核心要点

  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可以理解和操作的任务，从而实现求解器设计的自动化。这样可以减少对领域专家的依赖，并能够快速适应不同的PBO问题。

技术框架：AutoPBO框架主要包含以下几个模块：1) 问题编码模块：将PBO问题的实例编码成LLM可以理解的文本形式。2) LLM驱动的启发式生成模块：利用LLM生成候选的启发式策略。3) 评估模块：在给定的PBO问题实例上评估候选启发式策略的性能。4) 优化模块：根据评估结果，利用优化算法（如进化算法）迭代优化LLM，使其生成更有效的启发式策略。

关键创新：AutoPBO的关键创新在于将LLM引入到PBO求解器的设计过程中，实现了启发式策略的自动化生成和优化。与传统的手动设计方法相比，AutoPBO能够更快速、更有效地找到适合特定PBO问题的启发式策略。此外，AutoPBO还能够适应不同类型的PBO问题，具有更强的通用性。

关键设计：AutoPBO的关键设计包括：1) 如何将PBO问题编码成LLM可以理解的文本形式，例如使用自然语言描述问题的约束条件和目标函数。2) 如何设计LLM的提示(prompt)，使其能够生成有效的启发式策略，例如提供一些示例启发式策略或指导LLM生成特定类型的启发式策略。3) 如何设计评估函数，准确评估启发式策略的性能，例如使用求解器在一定时间内求解PBO问题，并根据求解结果计算评估值。4) 如何选择合适的优化算法，迭代优化LLM，例如使用进化算法或强化学习算法。

📊 实验亮点

AutoPBO在四个公共基准测试中进行了评估，包括真实世界基准、PB竞赛基准、整数线性规划优化基准和组合基准。实验结果表明，AutoPBO显著优于现有的局部搜索方法，例如NuPBO和OraSLS，并且与最先进的完整PB求解器（如PBO-IHS和RoundingSat）以及混合整数规划求解器（如Gurobi和SCIP）相比，保持了具有竞争力的性能。具体提升幅度未知，但结论是显著优于局部搜索方法。

🎯 应用场景

AutoPBO具有广泛的应用前景，可应用于组合优化、调度、资源分配等领域。通过自动化PBO求解器的设计，可以降低解决这些问题的成本，提高效率。未来，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.