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.
Formulating an optimization problem strongly affects final solution quality, yet good formulations usually require substantial expertise. Recent studies have explored automatically deriving optimization problems from natural-language descriptions, but existing benchmarks focus on settings where objectives and constraints can be written explicitly as mathematical expressions. Many practically important problems are naturally treated as black-box optimization (BBO) problems, in which only objective values are observable, and the functional form is unavailable. In BBO, search space design (as part of problem formulation) and optimization algorithm selection are crucial for problem-solving. Automating these processes with large language models (LLMs) remains challenging. We introduce Black-Box Optimization Word Problems (BBOWP), a novel problem setting in which a system must infer both a search space and an optimization algorithm from a natural-language description of a black-box optimization task. To support research on this setting, we establish the BBOWP Benchmark Suite (BBOWP-Bench), a dataset and evaluation framework for BBOWP. Each instance combines a natural-language problem description, an executable evaluation environment, and a human-designed reference formulation, allowing evaluation of both search-space design and algorithm selection. Using this benchmark, we evaluate LLMs on the joint formulation of search spaces and optimizers from natural-language descriptions across multiple BBO domains. We show that current LLMs vary their optimizer choice with the evaluation budget, though they sometimes struggle with search space design, particularly in identifying important variables and balancing their ranges when the problem description is less informative or the search space is highly problem-specific. Our code and dataset are available at https://github.com/shiralab/bbowp-bench.
Large Language Models (LLMs) have already been widely adopted for automated algorithm design, demonstrating strong abilities in generating and evolving algorithms across various fields. Existing work has largely focused on examining their effectiveness in solving specific problems, with search strategies primarily guided by adaptive prompt designs. In this paper, through investigating the token-wise attribution of the prompts to LLM-generated algorithmic code, we show that the embedded code examples and their associated strategy instructions have the strongest influence on the generated algorithms. Building upon this insight, we propose leveraging existing benchmark algorithms as strong priors to guide LLM-driven optimization. We evaluate this approach with three LLMs on two black-box optimization benchmarks: the pseudo-Boolean optimization suite (pbo) and the black-box optimization suite (bbob). Despite relying on a simple (1+1) elitist search, it obtains the best average rank in five of six benchmark--LLM settings against six state-of-the-art LLM-driven methods, including more sophisticated search strategies. Our findings highlight the value of integrating benchmarking studies to enhance both efficiency and robustness of the LLM-driven black-box optimization methods.
Qi Huang, Furong Ye, Ananta Shahane +2
Leiden Institute of Advanced Computer Science (LIACS), Leiden University, 2333 CC Leiden, The Netherlands
Large Language Models (LLMs) struggle to solve complex combinatorial problems through direct reasoning, so recent neuro-symbolic systems increasingly use them to synthesize executable solvers. A central design question is how the LLM should represent the solver, and whether it should also attempt to optimize search. We introduce CP-SynC-XL, a benchmark of 100 combinatorial problems (4,577 instances), and evaluate three solver-construction paradigms: native algorithmic search (Python), constraint modeling through a Python solver API (Python + OR-Tools), and declarative constraint modeling (MiniZinc + OR-Tools). We find a consistent representational divergence: Python + OR-Tools attains the highest correctness across LLMs, while MiniZinc + OR-Tools has lower absolute coverage despite using the same OR-Tools back-end. Native Python is the most likely to return a schema-valid solution that fails verification, whereas solver-backed paths preserve higher conditional fidelity. On the heuristic axis, prompting for search optimization yields only small median speed-ups (1.03-1.12x) and a strongly bimodal effect: many instances slow down, and correctness drops sharply on a long tail of problems. A paired code-level audit traces these regressions to a recurring heuristic trap. Under an efficiency-oriented prompt, the LLM may replace complete search with local approximations (Python), inject unverified bounds (Python + OR-Tools), or add redundant declarative machinery that overwhelms or over-constrains the model (MiniZinc + OR-Tools). These findings support a conservative design principle for LLM-generated combinatorial solvers: use the LLM primarily to formalize variables, constraints, and objectives for verified solvers, and separately check any LLM-authored search optimization before use.
Haoyu Wang, Yuliang Song, Tao Li +5
University of Pennsylvania · University of Toronto · Google DeepMind +1