Zhihui Xie, Xu Liu, Shuai Li

Multi-armed Bandit Algorithms for the Boolean Satisfiability Problem: A Survey

Introduction

Multi-armed bandit algorithms for the boolean satisfiability problem: a survey. Survey multi-armed bandit algorithms for the Boolean Satisfiability Problem (SAT). Learn how they enhance modern SAT solvers, balance exploration/exploitation, and their future research potential.

Abstract

This paper provides a survey of recent literature on the use of multi-armed bandit algorithms to solve the Boolean satisfiability problem (SAT), a well-known NP-complete problem with broad applications in academia and industry. The application of bandit algorithms in modern SAT solvers has achieved great success in recent years, as evidenced by the excellent performance of SAT solvers using bandit algorithms in SAT competitions. Bandit algorithms are classic randomized optimization algorithms that strike a balance between exploration and exploitation and can aid in designing and improving heuristics in SAT solvers. In this paper, we introduce several aspects of the application of bandit algorithms in modern SAT solvers, ranging from heuristic methods in CDCL and SLS solvers to strategies in parallel SAT solvers. The use of bandit algorithms in SAT solvers still holds great potential. In conclusion of the survey, we summarize the current issues and suggest possible future research directions.

Review

This survey paper addresses a highly relevant and impactful topic: the application of multi-armed bandit (MAB) algorithms to the Boolean Satisfiability Problem (SAT). SAT, being a canonical NP-complete problem with extensive applications across various domains, constantly benefits from advancements in solving techniques. The authors effectively highlight the significant success of MAB algorithms in modern SAT solvers, particularly noting their excellent performance in recent SAT competitions. This immediately establishes the practical relevance and timeliness of the survey, positioning MABs as a critical component in current high-performance SAT solving due to their ability to balance exploration and exploitation in designing and improving heuristics. The paper promises a comprehensive overview, delving into several crucial aspects of MAB integration within contemporary SAT solvers. Specifically, it aims to cover their deployment in heuristic methods for both Conflict-Driven Clause Learning (CDCL) and Stochastic Local Search (SLS) solvers, which represent the two dominant paradigms in SAT solving. Furthermore, the survey extends its scope to include strategies for parallel SAT solvers, demonstrating an appreciation for the evolving landscape of high-performance computing in this field. This broad coverage suggests that the survey will provide a holistic understanding of how MAB algorithms are being leveraged across different architectural and algorithmic approaches to SAT. As a survey, this paper offers substantial value by consolidating recent advancements and insights into a rapidly evolving area. By introducing various facets of MAB application, from core heuristics to parallelization strategies, it serves as an excellent resource for researchers and practitioners alike. The abstract concludes by emphasizing the "great potential" that MABs still hold in SAT solving, a crucial statement for any forward-looking survey. The commitment to summarizing current issues and suggesting possible future research directions further enhances its utility, guiding the reader towards unresolved challenges and promising avenues for further exploration. This positions the paper not just as a retrospective review, but as a proactive contribution that can stimulate future research and innovation in the field.

Full Text

Comments

You need to be logged in to post a comment.