  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.
