cs.AISep 4, 2025

AutoPBO: LLM-powered Optimization for Local Search PBO Solvers

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

Organizations: Institute of Software, Chinese Academy of Sciences, Beijing, China · Key Laboratory of System Software, Institute of Software, Chinese Academy of Sciences, Beijing, China · School of Computer Science and Technology, University of Chinese Academy of Sciences, Beijing, China · School of Data Science, Fudan University, Shanghai, China

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.

Figures & tables

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. BBOWP-Bench: Evaluating LLMs on Black-Box Optimization Word Problems

    May 20, 2026Yutaro Yamada, Kei Hiroshima, Nozomu Yoshinari +2Black-Box OptimizationNatural Language to Optimization Modeling

  2. From Heuristic Selection to Automated Algorithm Design: LLMs Benefit from Strong Priors

    Mar 3, 2026Qi Huang, Furong Ye, Ananta Shahane +2Large Language Model-Guided OptimizationAutomated Algorithm Discovery

  3. Formalize, Don't Optimize: The Heuristic Trap in LLM-Generated Combinatorial Solvers

    May 12, 2026Haoyu Wang, Yuliang Song, Tao Li +5Large Language Model-Guided OptimizationLLM-Based Program Synthesis