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.
翻译:部分 MaxSAT (PMS) 和 加权部分 MaxSAT (WPMS) 两者都是对 MaxSAT 典型的组合式组合式问题的实际概括。 在这项工作中,我们提出一种有效的远视概率抽样基于本地搜索算法,称为FPS, 称为(W)PMS。FPS 算法取代了在现有(W) PMS 本地搜索算法中翻转单一变量的机械化每个迭代步骤的机制,该算法被广泛用于现有的(W) PMS 本地搜索算法,并采用高视力本地搜索战略,并提供更高质量的本地最佳解决方案。 高视力战略采用使SAT 算法能够广泛和高效地直观地显示情况。 通过这种方法,FPSPS可以提供更多更好的搜索方向,并在不降低效率的情况下改进业绩。 广泛试验了(W) PMS 的所有基准,从最近四年的不完全的轨道上翻转一个变量,表明我们的方法大大超过 SATLE3.0 、 当地最先进的本地搜索算法,用于解决PSMS 和WPMS 的全局性搜索算法问题。 我们还三个类 ROMS 和最远的路径, ROMS 和最远的路径比 。 我们的路径与四个的路径比 MAS 和最远的路径比 的路径, MASATMS 和最远的路径与四个的路径比 的路径 。