We address Partial MaxSAT (PMS) and Weighted PMS (WPMS), two practical
generalizations of the MaxSAT problem, and propose a local search algorithm for
these problems, called BandMaxSAT, that applies a multi-armed bandit model to
guide the search direction. The bandit in our method is associated with all the
soft clauses in the input (W)PMS instance. Each arm corresponds to a soft
clause. The bandit model can help BandMaxSAT to select a good direction to
escape from local optima by selecting a soft clause to be satisfied in the
current step, that is, selecting an arm to be pulled. We further propose an
initialization method for (W)PMS that prioritizes both unit and binary clauses
when producing the initial solutions. Extensive experiments demonstrate that
BandMaxSAT significantly outperforms the state-of-the-art (W)PMS local search
algorithm SATLike3.0. Specifically, the number of instances in which BandMaxSAT
obtains better results is about twice that obtained by SATLike3.0. Moreover, we
combine BandMaxSAT with the complete solver TT-Open-WBO-Inc. The resulting
solver BandMaxSAT-c also outperforms some of the best state-of-the-art complete
(W)PMS solvers, including SATLike-c, Loandra and TT-Open-WBO-Inc.

本研究提出了一个名为 BandMaxSAT 的局部搜索算法，它应用多臂赌博机模型来引导搜索方向，特别适用于 Partial MaxSAT (PMS) 和 Weighted PMS (WPMS) 问题，相较于现有算法 SATLike3.0，实验证明 BandMaxSAT 在解决这些问题上更为优秀，与 TT-Open-WBO-Inc 结合可以获得更好的效果。

BandMaxSAT：具有多臂老虎机的局部搜索 MaxSAT 求解器

BandMaxSAT: A Local Search MaxSAT Solver with Multi-armed Bandit

Local search has been demonstrated as an efficient approach for two practical
generalizations of the MaxSAT problem, namely Partial MaxSAT (PMS) and Weighted
PMS (WPMS). In this work, we observe that most local search (W)PMS solvers
usually flip a single variable per iteration. Such a mechanism may lead to
relatively low-quality local optimal solutions, and may limit the diversity of
search directions to escape from local optima. To address this issue, we
propose a general strategy, called farsighted probabilistic sampling (FPS), to
replace the single flipping mechanism so as to boost the local search (W)PMS
algorithms. FPS considers the benefit of continuously flipping a pair of
variables in order to find higher-quality local optimal solutions. Moreover,
FPS proposes an effective approach to escape from local optima by preferring
the best to flip among the best sampled single variable and the best sampled
variable pair. Extensive experiments demonstrate that our proposed FPS strategy
significantly improves the state-of-the-art (W)PMS solvers, and FPS has an
excellent generalization capability to various local search MaxSAT solvers.

本文提出了一种名为 FPS 的策略，通过考虑连续翻转一对变量的好处来替换单一翻转机制，以提高本地搜索算法的效率，解决了局部最优解品质较低的问题，并通过最佳取样的方法避免了局部最优解，实验表明该方法极大地提高了最先进的 (W) PMS 解算器的性能。