.png){kind=icon}
Return
Optimizing local search-based partial MaxSAT solving via initial assignment prediction
.png){kind=icon}
PRE
AI
DOI：10.1007/s11432-023-3900-7.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 time. For 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.
Keywords:
MaxSAT
local search
initial assignment
incomplete method
assignment prediction
Journal
IF:
7.6
Papers:
4.9K
Citations:
8.9K
Organization
View more organizations
Cited Papers
ShareSaveShareSavePhytosterol Contents of Edible Oils and Their Contributions to Estimated Phytosterol Intake in the Chinese Diet.png)
Foods
OAAI
FoodsIF0
OAAIShareSaveShareSave View more