Partial MaxSAT (PMS) and Weighted PMS (WPMS) are two practical
generalizations of the MaxSAT problem. In this paper, we propose a local search
algorithm for these problems, called BandHS, which applies two multi-armed
bandits to guide the search directions when escaping local optima. One bandit
is combined with all the soft clauses to help the algorithm select to satisfy
appropriate soft clauses, and the other bandit with all the literals in hard
clauses to help the algorithm select appropriate literals to satisfy the hard
clauses. These two bandits can improve the algorithm's search ability in both
feasible and infeasible solution spaces. We further propose an initialization
method for (W)PMS that prioritizes both unit and binary clauses when producing
the initial solutions. Extensive experiments demonstrate the excellent
performance and generalization capability of our proposed methods, that greatly
boost the state-of-the-art local search algorithm, SATLike3.0, and the
state-of-the-art SAT-based incomplete solver, NuWLS-c.

本文提出了一种基于多臂赌博机的本地搜索算法 BandHS 用来解决 MaxSAT 及其两个泛化问题，和一个初始化方法优化算法的表现。经过大量实验证明，本文提出的方法在解决 MaxSAT 问题时表现出色。