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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

SNRWLS: Improve (W)PMS Solver with Weighting Strategies Related to Number of Soft Clauses

  • Shuhao Chen,
  • Menghua Jiang,
  • Yin Chen

摘要

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.