CCEHC: An efficient local search algorithm for weighted partial maximum satisfiability

详细信息    查看全文

• 作者：Chuan Luo^a ; ^b ; ^{chuanluosaber@gmail.com} ; Shaowei Cai^c ; ^{shaoweicai.cs@gmail.com} ; Kaile Su^d ; ^e ; ^{k.su@griffith.edu.au} ; Wenxuan Huang^f ; ^{key01027@mit.edu}
• 关键词：Local search ; Weighted partial maximum satisfiability ; Emphasis on hard clauses
• 刊名：Artificial Intelligence
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：243
• 期：Complete
• 页码：26-44
• 全文大小：560 K
• 卷排序：243

文摘

Weighted maximum satisfiability and (unweighted) partial maximum satisfiability (PMS) are two significant generalizations of maximum satisfiability (MAX-SAT), and weighted partial maximum satisfiability (WPMS) is the combination of the two, with more important applications in practice. Recently, great breakthroughs have been made on stochastic local search (SLS) for weighted MAX-SAT and PMS, resulting in several state-of-the-art SLS algorithms CCLS, Dist and DistUP. However, compared to the great progress of SLS on weighted MAX-SAT and PMS, the performance of SLS on WPMS lags far behind. In this paper, we present a new SLS algorithm named CCEHC for WPMS. CCEHC employs an extended framework of CCLS with a heuristic emphasizing hard clauses, called EHC. With strong accents on hard clauses, EHC has three components: a variable selection mechanism focusing on configuration checking based only on hard clauses, a weighting scheme for hard clauses, and a biased random walk component. Extensive experiments demonstrate that CCEHC significantly outperforms its state-of-the-art SLS competitors. Further experimental results on comparing CCEHC with a state-of-the-art complete solver show the effectiveness of CCEHC on a number of application WPMS instances, and indicate that CCEHC might be beneficial in practice. Also, empirical analyses confirm the effectiveness of each component underlying the EHC heuristic.