<p>Pure MaxSAT (PureMS), an important subclass of the NP-hard combinatorial optimization problem, has wide applications, especially in classic subset problems. Despite its practical importance, state-of-the-art algorithms for the PureMS can hardly solve large and hard instances effectively, mainly due to the characteristics of its special structure. In this paper, we develop an efficient local search algorithm for the PureMS namely DPSLS, which has two main ideas. First, we propose a reasoning initialization procedure which makes fully use of the classic unit propagation to generate a good initial point. Second, a two-goal variable selection strategy is designed during the search process, whose aim is to effectively handle falsified soft and hard clauses, respectively. Experimental results show that our algorithm significantly outperforms state-of-the-art algorithms in terms of solution quality, achieving superior results in 78.0% of unweighted instances, 64.5% of weighted instances from the MaxSAT Evaluations 2018-2021, and 90.9% of SCP instances.</p>

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

DPSLS: an efficient local search algorithm for pure MaxSAT

  • Huisi Zhou,
  • Xinyu Zhang,
  • Wei Hu,
  • Dan Zhu,
  • Liwei Wang

摘要

Pure MaxSAT (PureMS), an important subclass of the NP-hard combinatorial optimization problem, has wide applications, especially in classic subset problems. Despite its practical importance, state-of-the-art algorithms for the PureMS can hardly solve large and hard instances effectively, mainly due to the characteristics of its special structure. In this paper, we develop an efficient local search algorithm for the PureMS namely DPSLS, which has two main ideas. First, we propose a reasoning initialization procedure which makes fully use of the classic unit propagation to generate a good initial point. Second, a two-goal variable selection strategy is designed during the search process, whose aim is to effectively handle falsified soft and hard clauses, respectively. Experimental results show that our algorithm significantly outperforms state-of-the-art algorithms in terms of solution quality, achieving superior results in 78.0% of unweighted instances, 64.5% of weighted instances from the MaxSAT Evaluations 2018-2021, and 90.9% of SCP instances.