CCEHC: An Efficient Local Search Algorithm for Weighted Partial Maximum Satisfiability (Extended Abstract)

CCEHC: An Efficient Local Search Algorithm for Weighted Partial Maximum Satisfiability (Extended Abstract)

Chuan Luo, Shaowei Cai, Kaile Su, Wenxuan Huang

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Journal track. Pages 5030-5034. https://doi.org/10.24963/ijcai.2017/716

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.
Keywords:
Constraints and Satisfiability: Constraint Optimisation
Combinatorial & Heuristic Search: Heuristic Search
Combinatorial & Heuristic Search: Combinatorial search/optimisation