CCEHC: An Efficient Local Search Algorithm for Weighted Partial Maximum Satisfiability (Extended Abstract)
Abstract
Weighted partial maximum satisfiability (WPMS) is a significant generalization of maximum satisfiability (MAX-SAT), with many important applications. Recently, breakthroughs have been made on stochastic local search (SLS) for weighted MAX-SAT and (unweighted) partial MAX-SAT (PMS). However, the performance of SLS for WPMS lags far behind. In this work, we present a new SLS algorithm named CCEHC for WPMS. CCEHC is mainly based on a heuristic emphasizing hard clauses, which has three components: a variable selection mechanism focusing on configuration checking based only on hard clauses, a weighting scheme for hard clauses, and a biased random walk component. Experiments show that CCEHC significantly outperforms its state-of-the-art SLS competitors. Experiments comparing CCEHC with a state-of-the-art complete solver indicate the effectiveness of CCEHC on a number of application WPMS instances.
Cite
Text
Luo et al. "CCEHC: An Efficient Local Search Algorithm for Weighted Partial Maximum Satisfiability (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2017. doi:10.24963/IJCAI.2017/716Markdown
[Luo et al. "CCEHC: An Efficient Local Search Algorithm for Weighted Partial Maximum Satisfiability (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2017.](https://mlanthology.org/ijcai/2017/luo2017ijcai-ccehc/) doi:10.24963/IJCAI.2017/716BibTeX
@inproceedings{luo2017ijcai-ccehc,
title = {{CCEHC: An Efficient Local Search Algorithm for Weighted Partial Maximum Satisfiability (Extended Abstract)}},
author = {Luo, Chuan and Cai, Shaowei and Su, Kaile and Huang, Wenxuan},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2017},
pages = {5030-5034},
doi = {10.24963/IJCAI.2017/716},
url = {https://mlanthology.org/ijcai/2017/luo2017ijcai-ccehc/}
}