资源论文Solving (Weighted) Partial MaxSAT by Dynamic Local Search for SAT Zhendong Lei and Shaowei Cai?

Solving (Weighted) Partial MaxSAT by Dynamic Local Search for SAT Zhendong Lei and Shaowei Cai?

2019-11-05 | |  99 |   50 |   0
Abstract Partial MaxSAT (PMS) generalizes SAT and MaxSAT by introducing hard clauses and soft clauses. PMS and Weighted PMS (WPMS) have many important real world applications. Local search is one popular method for solving (W)PMS. Recent studies on specialized local search for (W)PMS have led to significant improvements. But such specialized algorithms are complicated with the concepts tailored for hard and soft clauses. In this work, we propose a dynamic local search algorithm, which exploits the structure of (W)PMS by a carefully designed clause weighting scheme. Our solver SATLike adopts a local search framework for SAT and does not need any specialized concept for (W)PMS. Experiments on PMS and WPMS benchmarks from the MaxSAT Evaluations (MSE) 2016 and 2017 show that SATLike significantly outperforms state of the art local search solvers. Also, SATLike significantly narrows the gap between the performance of local search solvers and complete solvers on industrial benchmarks, and performs better than state of the art complete solvers on the MSE2017 benchmarks.

上一篇:Solving Exist-Random Quantified Stochastic Boolean Satisfiability via Clause Selection

下一篇:Core-Guided Minimal Correction Set and Core Enumeration

用户评价
全部评价

热门资源

  • The Variational S...

    Unlike traditional images which do not offer in...

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...

  • Rating-Boosted La...

    The performance of a recommendation system reli...