arXiv cs.AI· Yi Chu, Jinyuan Li, Yiwen Sun, Mengchuan Zou, Shaowei Cai·· 4 小时前AI 评分24
AutoPBO:用 LLM 自动优化局部搜索 PBO 求解器
AutoPBO: LLM-powered Optimization for Local Search PBO Solvers
AI 导读
AutoPBO 是一个由 LLM 驱动的框架,用于自动增强伪布尔优化(PBO)局部搜索求解器的内部启发式设计。在四个公开基准(含一个真实世界基准、PB 竞赛基准、整数线性规划优化基准和构造组合基准)上,AutoPBO 相比 NuPBO、OraSLS 等局部搜索方法取得显著提升,并与 PBO-IHS、RoundingSat、Gurobi、SCIP 等六个 SOTA 求解器保持竞争力。
正文 · 原文
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