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
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
Figure 1: Architecture of AutoPBO. With a structuralized local search PBO solver as input, AutoPBO implements greedy strategy to optimize heuristic functions iteratively. For each iteration, AutoPBO employs the original solver code to instantaneously create an understanding and recommendations for heuristic functions, subsequently engages in code generation and performance assessment by three agents. Upon completion, AutoPBO returns the optimal solver code.
Table 1: Agent Tasks and Tips Overview
Benchmark
StructPBO
AutoPBO
#win
avg_score
#win
avg_score
Real-world
17
0.9962
29
0.9998
CRAFT
488
0.9472
513
0.9474
MIPLIB
101
0.8450
112
0.8598
PB16
697
0.8272
775
0.8447
Total
1303
0.8738
1429
0.8849
Table 2: AutoPBO vs StructPBO Performance Comparison (By Benchmark)
Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.