SNRWLS: Improve (W)PMS Solver with Weighting Strategies Related to Number of Soft Clauses
摘要
Maximum Satisfiability Problem (MaxSAT) is a fundamental constraint optimization problem that plays a critical role in various real-world applications. (Weighted) Partial MaxSAT problem, denoted as (W)PMS, is the practical generalization of MaxSAT, and stochastic local search (SLS) algorithms are commonly used to solve (W)PMS problems. In this work, we study the deficiencies in the previous SLS solver and improve some of its strategies to obtain a new SLS solver, named SNRWLS, which includes three new strategies. First, we propose a strategy of parameter adjustment, which tunes some parameters of the solver when the search reaches a fixed time point. Second, we propose an initialization method that utilizes the assignment information of variables in obtained solutions to produce an initial assignment. Third, we propose a new weighting strategy and determine whether to apply its methods based on the number of soft clauses. Experimental results show that SNRWLS significantly outperforms state-of-the-art SLS solvers.