Incorporating Multi-armed Bandit with Local Search for MaxSAT

• URL: http://arxiv.org/abs/2211.16011v1
• Date: Tue, 29 Nov 2022 08:19:26 GMT
• Title: Incorporating Multi-armed Bandit with Local Search for MaxSAT
• Authors: Jiongzhi Zheng and Kun He and Jianrong Zhou and Yan Jin and Chu-Min Li and Felip Many\`a
• Abstract summary: Two generalizations of the MaxSAT problem: Partial MaxSAT (PMS) and Weighted PMS (WPMS) 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. These two bandits can improve the algorithm's search ability in both feasible and infeasible solution spaces.
• Score: 16.371916145216737
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Rethinking the Soft Conflict Pseudo Boolean Constraint on MaxSAT Local Search Solvers [20.866863965121013]
  MaxSAT is an optimization version of the famous NP-complete Satisfiability problem (SAT) We propose a new local search algorithm called SPB-MaxSAT that provides new perspectives for clause weighting on MaxSAT local search solvers.
  arXiv  Detail & Related papers  (2024-01-19T09:59:02Z)
• General Method for Solving Four Types of SAT Problems [12.28597116379225]
  Existing methods provide varying algorithms for different types of Boolean satisfiability problems (SAT) This study proposes a unified framework DCSAT based on integer programming and reinforcement learning (RL) algorithm to solve different types of SAT problems.
  arXiv  Detail & Related papers  (2023-12-27T06:09:48Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• DPMS: An ADD-Based Symbolic Approach for Generalized MaxSAT Solving [45.21499915442282]
  We propose a novel dynamic-programming approach for solving generalized MaxSAT problems with hybrid constraints. Our versatile framework admits many generalizations of CNF-MaxSAT, such as MaxSAT, Min-MaxSAT, and MinSAT with hybrid constraints. Empirical results indicate that DPMS is able to solve certain problems quickly, where other algorithms based on various techniques all fail.
  arXiv  Detail & Related papers  (2022-05-08T00:31:53Z)
• BandMaxSAT: A Local Search MaxSAT Solver with Multi-armed Bandit [16.371916145216737]
  We propose a local search algorithm called BandMaxSAT, that applies a multi-armed bandit to guide the search direction. Extensive experiments demonstrate that BandMaxSAT significantly outperforms the state-of-the-art (W)PMS local search algorithm SATLike3.0. 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.
  arXiv  Detail & Related papers  (2022-01-14T16:32:39Z)
• Farsighted Probabilistic Sampling based Local Search for (Weighted) Partial MaxSAT [5.529868797285073]
  Partial MaxSAT (PMS) and Weighted Partial MaxSAT (WPMS) are practical generalizations to the typical problem of MaxSAT. We propose an effective farsighted probabilistic sampling based local search algorithm called FPS for solving these two problems.
  arXiv  Detail & Related papers  (2021-08-23T07:41:56Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Incomplete MaxSAT Approaches for Combinatorial Testing [0.0]
  We present a Satisfiability (SAT)-based approach for building Mixed Covering Arrays with Constraints of minimum length. This problem is central in Combinatorial Testing for the detection of system failures.
  arXiv  Detail & Related papers  (2021-05-26T14:00:56Z)
• Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
  We provide a simple method to combine bandit algorithms. Our approach is based on a "meta-UCB" procedure that treats each of $N$ individual bandit algorithms as arms in a higher-level $N$-armed bandit problem.
  arXiv  Detail & Related papers  (2020-12-24T05:36:29Z)
• Double Explore-then-Commit: Asymptotic Optimality and Beyond [101.77632893858063]
  We study the multi-armed bandit problem with subgaussian rewards. We show that a variant of the explore-then-commit (ETC) algorithm can achieve the optimality for multi-armed bandit problems.
  arXiv  Detail & Related papers  (2020-02-21T08:07:56Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  We propose the setting of extreme algorithm selection (XAS) where we consider fixed sets of thousands of candidate algorithms. We assess the applicability of state-of-the-art AS techniques to the XAS setting and propose approaches leveraging a dyadic feature representation.
  arXiv  Detail & Related papers  (2020-01-29T09:40:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.