# AutoPBO: LLM-powered Optimization for Local Search PBO Solvers

arXiv: https://arxiv.org/abs/2509.04007 · HTML: https://mlsanity.com/paper/2509.04007/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 23 references that are in the map.
- First posted on arXiv 4 Sep 2025.

## Builds on (most cited first, 4 of 4)

- [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://mlsanity.com/paper/2506.13131/) (2025)
- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [DeciLS-PBO: an Effective Local Search Method for Pseudo-Boolean Optimization](https://mlsanity.com/paper/2301.12251/) (2023)
- [ParLS-PBO: A Parallel Local Search Solver for Pseudo Boolean Optimization](https://mlsanity.com/paper/2407.21729/) (2024)

## Built on by (most cited first, 2 of 2)

- [From Heuristic Selection to Automated Algorithm Design: LLMs Benefit from Strong Priors](https://mlsanity.com/paper/2603.02792/) (2026)
- [MiniOpt: Reasoning to Model and Solve General Optimization Problems with Limited Resources](https://mlsanity.com/paper/2606.25832/) (2026)

## Abstract (arXiv)

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.