# Incorporating Multi-armed Bandit with Local Search for MaxSAT

arXiv: https://arxiv.org/abs/2211.16011 · HTML: https://mlsanity.com/paper/2211.16011/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 41 references that are in the map.
- First posted on arXiv 29 Nov 2022.

## Builds on (most cited first, 6 of 6)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Learning Features and Abstract Actions for Computing Generalized Plans](https://mlsanity.com/paper/1811.07231/) (2018)
- [Randomized Allocation with Nonparametric Estimation for Contextual Multi-Armed Bandits with Delayed Rewards](https://mlsanity.com/paper/1902.00819/) (2019)
- [BandMaxSAT: A Local Search MaxSAT Solver with Multi-armed Bandit](https://mlsanity.com/paper/2201.05544/) (2022)
- [Incomplete MaxSAT Approaches for Combinatorial Testing](https://mlsanity.com/paper/2105.12552/) (2021)
- [Cascaded Algorithm-Selection and Hyper-Parameter Optimization with Extreme-Region Upper Confidence Bound Bandit](https://mlsanity.com/paper/1905.13703/) (2019)

## Abstract (arXiv)

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.