.png){kind=icon}
.png){kind=icon}
Return
DPSLS: an efficient local search algorithm for pure MaxSAT
.png){kind=icon}
PRE
AI
DOI：10.1007/s12083-025-02021-9.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
MaxSAT
SCP
Pure MaxSAT
Local search
NP-hard
Journal
IF:
2.6
Papers:
2.2K
Citations:
2.9K