# ParLS-PBO: A Parallel Local Search Solver for Pseudo Boolean Optimization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 56 references that are in the map.
- First posted on arXiv 31 Jul 2024.

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

- [SMAC3: A Versatile Bayesian Optimization Package for Hyperparameter Optimization](https://mlsanity.com/paper/2109.09831/) (2021)
- [The SCIP Optimization Suite 9.0](https://mlsanity.com/paper/2402.17702/) (2024)
- [ARJA: Automated Repair of Java Programs via Multi-Objective Genetic Programming](https://mlsanity.com/paper/1712.07804/) (2017)
- [Generalized Totalizer Encoding for Pseudo-Boolean Constraints](https://mlsanity.com/paper/1507.05920/) (2015)
- [DeciLS-PBO: an Effective Local Search Method for Pseudo-Boolean Optimization](https://mlsanity.com/paper/2301.12251/) (2023)

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

- [AutoPBO: LLM-powered Optimization for Local Search PBO Solvers](https://mlsanity.com/paper/2509.04007/) (2025)

## Abstract (arXiv)

As a broadly applied technique in numerous optimization problems, recently, local search has been employed to solve Pseudo-Boolean Optimization (PBO) problem. A representative local search solver for PBO is LSPBO. In this paper, firstly, we improve LSPBO by a dynamic scoring mechanism, which dynamically strikes a balance between score on hard constraints and score on the objective function. Moreover, on top of this improved LSPBO , we develop the first parallel local search PBO solver. The main idea is to share good solutions among different threads to guide the search, by maintaining a pool of feasible solutions. For evaluating solutions when updating the pool, we propose a function that considers both the solution quality and the diversity of the pool. Furthermore, we calculate the polarity density in the pool to enhance the scoring function of local search. Our empirical experiments show clear benefits of the proposed parallel approach, making it competitive with the parallel version of the famous commercial solver Gurobi.