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

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 39 references that are in the map.
- First posted on arXiv 14 Jan 2022.

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

- [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)
- [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)

## Built on by (most cited first, 6 of 6)

- [Application of AI to formal methods - an analysis of current trends](https://mlsanity.com/paper/2411.14870/) (2024)
- [Incorporating Multi-armed Bandit with Local Search for MaxSAT](https://mlsanity.com/paper/2211.16011/) (2022)
- [Better Understandings and Configurations in MaxSAT Local Search Solvers via Anytime Performance Analysis](https://mlsanity.com/paper/2403.06568/) (2024)
- [Integer Linear Programming Preprocessing for Maximum Satisfiability](https://mlsanity.com/paper/2506.06216/) (2025)
- [Enhancing Local Search for MaxSAT with Deep Differentiation Clause Weighting](https://mlsanity.com/paper/2512.05619/) (2025)
- [Offline Local Search for Online Stochastic Bandits](https://mlsanity.com/paper/2604.09423/) (2026)

## Abstract (arXiv)

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.