NuDist: An Efficient Local Search Algorithm for (Weighted) Partial MaxSAT. (15th August 2019)

• Record Type: Journal Article
• Authors: Lei, Zhendong; Cai, Shaowei
• Is Part Of: Computer journal. Volume 63:Number 9(2020)
• Page Start: 1321
• Page End: 1337
• Publication Date: 2019-08-15
• Subjects: local search -- partial maximum satisfiability; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxz063
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: Maximum satisfiability (MaxSAT) is the optimization version of the satisfiability (SAT). Partial MaxSAT (PMS) generalizes SAT and MaxSAT by introducing hard and soft clauses, while Weighted PMS (WPMS) is the weighted version of PMS where each soft clause has a weight. These two problems have many important real-world applications. Local search is a popular method for solving (W)PMS. Recently, significant progress has been made in this direction by tailoring local search for (W)PMS, and a representative algorithm is the Dist algorithm. In this paper, we propose two ideas to improve Dist, including a clause-weighting scheme and a variable-selection heuristic. The resulting algorithm is called NuDist. Extensive experiments on PMS and WPMS benchmarks from the MaxSAT Evaluations (MSE) 2016 and 2017 show that NuDist significantly outperforms state-of-the-art local search solvers and performs better than state-of-the-art complete solvers including Open-WBO and WPM3 on MSE 2017 benchmarks. Also, empirical analyses confirm the effectiveness of the proposed ideas.