Optimizing local search-based partial MaxSAT solving via initial assignment prediction

作     者：Chanjuan LIU Guangyuan LIU Chuan LUO Shaowei CAI Zhendong LEI Wenjie ZHANG Yi CHU Guojing ZHANG 

作者机构：School of Computer Science and TechnologyDalian University of Technology School of SoftwareBeihang University Institute of SoftwareChinese Academy of Sciences School of Computer SciencePeking University 

出 版 物：《Science China(Information Sciences)》 (中国科学:信息科学(英文版))

年 卷 期：2025年第68卷第2期

页      面：59-73页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：supported in part by National Key Research and Development Program of China (Grant No. 2022YFB4502003) National Natural Science Foundation of China (Grant Nos. 62172072, 62202025, 62122078, 62302492) Natural Science Foundation of Liaoning Province of China (Grant No. 2021-MS-114) CCF-Huawei Populus Grove Fund (Grant No. CCF-HuaweiSY202311) Frontier Cross Fund Project of Beihang University 

主　　题：MaxSAT local search initial assignment incomplete method assignment prediction 

摘      要：Partial maximum satisfiability(PMS) is a significant generalization of Boolean satisfiability(SAT) and maximum satisfiability(MaxSAT), by introducing hard clauses and soft clauses. Compared with SAT and MaxSAT, the PMS problem has more real-world applications where both hard and soft constraints are involved. Local search is an effective incomplete method for solving PMS and is useful for important domains where good-quality solutions are desired within reasonable *** local search PMS solvers, the approach for initial assignment generation is crucial because its effectiveness significantly affects practical performance. In this study, we propose a novel initial assignment prediction approach, called InitPMS. When predicting an assignment for PMS, InitPMS considers the specific structure of PMS instances, i.e., distinguishing hard and soft clauses. Our experiments on extensive PMS instances from MaxSAT evaluations(MSEs) 2020 and 2021 show that InitPMS significantly boosts the performance of five state-of-the-art local search PMS solvers, demonstrating its generality. In addition,our results indicate that incorporating InitPMS could improve the performance of one of the best incomplete PMS solvers in MaxSAT Evaluation 2021, indicating that InitPMS might help advance the state of the art in PMS solving.