Farsighted Probabilistic Sampling based Local Search for (Weighted)
  Partial MaxSAT
  Partial MaxSAT (PMS) and Weighted Partial MaxSAT (WPMS) are both practical
generalizations to the typical combinatorial problem of MaxSAT. In this work,
we propose an effective farsighted probabilistic sampling based local search
algorithm called FPS for solving these two problems, denoted as (W)PMS. The FPS
algorithm replaces the mechanism of flipping a single variable per iteration
step, that is widely used in existing (W)PMS local search algorithms, with the
proposed farsighted local search strategy, and provides higher-quality local
optimal solutions. The farsighted strategy employs the probabilistic sampling
technique that allows the algorithm to look-ahead widely and efficiently. In
this way, FPS can provide more and better search directions and improve the
performance without reducing the efficiency. Extensive experiments on all the
benchmarks of (W)PMS problems from the incomplete track of recent four years of
MaxSAT Evaluations demonstrate that our method significantly outperforms
SATLike3.0, the state-of-the-art local search algorithm, for solving both the
PMS and WPMS problems. We furthermore do comparison with the extended solver of
SATLike, SATLike-c, which is the champion of three categories among the total
four (PMS and WPMS categories, each associated with two time limits) of the
incomplete track in the recent MaxSAT Evaluation (MSE2021). We replace the
local search component in SATLike-c with the proposed farsighted sampling local
search approach, and the resulting solver FPS-c also outperforms SATLike-c for
solving both the PMS and WPMS problems.
