Incorporating Multi-armed Bandit with Local Search for MaxSAT
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.
Code (1)
Tasks
Multi-Armed BanditsSimilar Papers 제목 키워드 기반
Evolutionary Multi-Armed Bandits with Genetic Thompson Sampling
As two popular schools of machine learning, online learning and evolutionary computations have become two important driving forces behind real-world decision making engines for applications in biomedicine, economics, and…
Decision MakingEvolutionary AlgorithmsMulti-Armed BanditsSequential Decision Making+1BandMaxSAT: A Local Search MaxSAT Solver with Multi-armed Bandit
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 …
Expanding on Repeated Consumer Search Using Multi-Armed Bandits and Secretaries
We seek to take a different approach in deriving the optimal search policy for the repeated consumer search model found in Fishman and Rob (1995) with the main motivation of dropping the assumption of prior knowledge of …
Multi-Armed BanditsDecentralized Stochastic Multi-Player Multi-Armed Walking Bandits
Multi-player multi-armed bandit is an increasingly relevant decision-making problem, motivated by applications to cognitive radio systems. Most research for this problem focuses exclusively on the settings that players h…
Decision MakingDistributed OptimizationGenetic multi-armed bandits: a reinforcement learning approach for discrete optimization via simulation
This paper proposes a new algorithm, referred to as GMAB, that combines concepts from the reinforcement learning domain of multi-armed bandits and random search strategies from the domain of genetic algorithms to solve d…
Multi-Armed BanditsStochastic Optimization