MaxSAT is an optimization version of the famous NP-complete Satisfiability
problem (SAT). Algorithms for MaxSAT mainly include complete solvers and local
search incomplete solvers. In many complete solvers, once a better solution is
found, a Soft conflict Pseudo Boolean (SPB) constraint will be generated to
enforce the algorithm to find better solutions. In many local search
algorithms, clause weighting is a key technique for effectively guiding the
search directions. In this paper, we propose to transfer the SPB constraint
into the clause weighting system of the local search method, leading the
algorithm to better solutions. We further propose an adaptive clause weighting
strategy that breaks the tradition of using constant values to adjust clause
weights. Based on the above methods, we propose a new local search algorithm
called SPB-MaxSAT that provides new perspectives for clause weighting on MaxSAT
local search solvers. Extensive experiments demonstrate the excellent
performance of the proposed methods.

本研究使用 MaxSAT 问题中的 SPB 约束和子句权重技术，提出了一种新的局部搜索算法 SPB-MaxSAT，为 MaxSAT 局部搜索求解器的子句权重方法提供了新的视角和优秀的性能。