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 satisfi-
ability (MAX-SAT), with many important applications. Recently, breakthroughs have been made on
stochastic local search (SLS) for weighted MAXSAT 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