NuWLS: Improving Local Search for (Weighted) Partial MaxSAT by New Weighting Techniques


  • Yi Chu Institute of Software, Chinese Academy of Sciences, China
  • Shaowei Cai State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, China School of Computer Science and Technology, University of Chinese Academy of Sciences, China
  • Chuan Luo School of Software, Beihang University, China



CSO: Constraint Optimization, CSO: Search, CSO: Solvers and Tools, SO: Heuristic Search, SO: Local Search


Maximum Satisfiability (MaxSAT) is a prototypical constraint optimization problem, and its generalized version is the (Weighted) Partial MaxSAT problem, denoted as (W)PMS, which deals with hard and soft clauses. Considerable progress has been made on stochastic local search (SLS) algorithms for solving (W)PMS, which mainly focus on clause weighting techniques. In this work, we identify two issues of existing clause weighting techniques for (W)PMS, and propose two ideas correspondingly. First, we observe that the initial values of soft clause weights have a big effect on the performance of the SLS solver for solving (W)PMS, and propose a weight initialization method. Second, we propose a new clause weighting scheme that for the first time employs different conditions for updating hard and soft clause weights. Based on these two ideas, we develop a new SLS solver for (W)PMS named NuWLS. Through extensive experiments, NuWLS performs much better than existing SLS solvers on all 6 benchmarks from the incomplete tracks of MaxSAT Evaluations (MSEs) 2019, 2020, and 2021. In terms of the number of winning instances, NuWLS outperforms state-of-the-art SAT-based incomplete solvers on all the 6 benchmarks. More encouragingly, a hybrid solver that combines NuWLS and an SAT-based solver won all four categories in the incomplete track of the MaxSAT Evaluation 2022.




How to Cite

Chu, Y., Cai, S., & Luo, C. (2023). NuWLS: Improving Local Search for (Weighted) Partial MaxSAT by New Weighting Techniques. Proceedings of the AAAI Conference on Artificial Intelligence, 37(4), 3915-3923.



AAAI Technical Track on Constraint Satisfaction and Optimization