跳到正文
arXiv cs.AI· Yi Chu, Jinyuan Li, Yiwen Sun, Mengchuan Zou, Shaowei Cai·· 2 小时前AI 评分34

AutoPBO:用 LLM 自动优化局部搜索 PBO 求解器

AutoPBO: LLM-powered Optimization for Local Search PBO Solvers

AI 导读

研究者提出 AutoPBO,一个利用大语言模型自动增强伪布尔优化(PBO)局部搜索求解器的框架。在四个公开基准上与 NuPBO、OraSLS、PBO-IHS、RoundingSat、Gurobi、SCIP 六个先进求解器对比,AutoPBO 显著优于以往局部搜索方法,并与最先进求解器性能相当。

正文 · 原文

View PDF HTML (experimental)

Abstract: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.
Comments: Author order updated. No changes to the scientific content
Subjects: Artificial Intelligence (cs.AI)
Cite as: arXiv:2509.04007 [cs.AI]
  (or arXiv:2509.04007v2 [cs.AI] for this version)
  https://doi.org/10.48550/arXiv.2509.04007

arXiv-issued DOI via DataCite

Submission history

From: Jinyuan Li [view email]
[v1] Thu, 4 Sep 2025 08:38:42 UTC (860 KB)
[v2] Tue, 17 Nov 2026 12:20:04 UTC (860 KB)

来源:arXiv cs.AI · arxiv.org