Abstract
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 dynamicallystrikes a balance between score on hard constraints and score on the objectivefunction. Moreover, on top of this improved LSPBO , we develop the first parallel localsearch PBO solver. The main idea is to share good solutions among differentthreads to guide the search, by maintaining a pool of feasible solutions. Forevaluating solutions when updating the pool, we propose a function thatconsiders both the solution quality and the diversity of the pool. Furthermore,we calculate the polarity density in the pool to enhance the scoring functionof local search. Our empirical experiments show clear benefits of the proposedparallel approach, making it competitive with the parallel version of thefamous commercial solver Gurobi.