Abstract
The Partial MAX-SAT Problem (PMSAT) is a variant of the MAX-SAT problem that consists of two CNF formulas defined over the same variable set. Its solution must satisfy all clauses of the first formula and as many clauses in the second formula as possible. This study is concerned with the PMSAT solution in setting a two-phase stochastic local search method that takes advantage of an estimated backbone variables of the problem. First experiments conducted on PMSAT instances derived from SAT instances indicate that this new method offers significant performance benefits over state-of-the-art PMSAT techniques.