Back to Search
Start Over
Initial Solution Generation and Diversified Variable Picking in Local Search for (Weighted) Partial MaxSAT.
- Source :
- Entropy; Dec2022, Vol. 24 Issue 12, p1846, 16p
- Publication Year :
- 2022
-
Abstract
- The (weighted) partial maximum satisfiability ((W)PMS) problem is an important generalization of the classic problem of propositional (Boolean) satisfiability with a wide range of real-world applications. In this paper, we propose an initialization and a diversification strategy to improve local search for the (W)PMS problem. Our initialization strategy is based on a novel definition of variables' structural entropy, and it aims to generate a solution that is close to a high-quality feasible one. Then, our diversification strategy picks a variable in two possible ways, depending on a parameter: continuing to pick variables with the best benefits or focusing on a clause with the greatest penalty and then selecting variables probabilistically. Based on these strategies, we developed a local search solver dubbed ImSATLike , as well as a hybrid solver ImSATLike-TT , and experimental results on (weighted) partial MaxSAT instances in recent MaxSAT Evaluations show that they outperform or have nearly the same performances as state-of-the-art local search and hybrid competitors, respectively, in general. Furthermore, we carried out experiments to confirm the individual impacts of each proposed strategy. [ABSTRACT FROM AUTHOR]
- Subjects :
- ENTROPY
HEURISTIC
GENERALIZATION
Subjects
Details
- Language :
- English
- ISSN :
- 10994300
- Volume :
- 24
- Issue :
- 12
- Database :
- Complementary Index
- Journal :
- Entropy
- Publication Type :
- Academic Journal
- Accession number :
- 160984358
- Full Text :
- https://doi.org/10.3390/e24121846