New Boolean satisfiability problem heuristic strategy: Minimal Positive Negative Product Strategy

2023-10-26 · Qun Zhao, Xintao Wang, Menghui Yang

This study presents a novel heuristic algorithm called the "Minimal Positive Negative Product Strategy" to guide the CDCL algorithm in solving the Boolean satisfiability problem. It provides a mathematical explanation for the superiority of this algorithm over widely used heuristics such as the Dynamic Largest Individual Sum (DLIS) and the Variable State Independent Decaying Sum (VSIDS). Experimental results further confirm the effectiveness of this heuristic strategy in problem-solving.

📄 PDF Abstract BibTeX arXiv:2310.18370

Code (0)

등록된 구현이 없습니다.

Learning Local Search Heuristics for Boolean Satisfiability

2019-12-01 · NeurIPS 2019 12 · Emre Yolcu, Barnabas Poczos

We present an approach to learn SAT solver heuristics from scratch through deep reinforcement learning with a curriculum. In particular, we incorporate a graph neural network in a stochastic local search algorithm to act…

Deep Reinforcement Learning Graph Neural Network reinforcement-learning Reinforcement Learning+2

SATformer: Transformer-Based UNSAT Core Learning

2022-09-02 · Zhengyuan Shi, Min Li, Yi Liu, Sadaf Khan 외

This paper introduces SATformer, a novel Transformer-based approach for the Boolean Satisfiability (SAT) problem. Rather than solving the problem directly, SATformer approaches the problem from the opposite direction by …

Graph Neural Network Multi-Task Learning

Graph Neural Networks for Reasoning 2-Quantified Boolean Formulas

2019-09-25 · Fei Wang, Zhanfu Yang, Ziliang Chen, Guannan Wei 외

It is valuable yet remains challenging to apply neural networks in logical reasoning tasks. Despite some successes witnessed in learning SAT (Boolean Satisfiability) solvers for propositional logic via Graph Neural Netwo…

Logical Reasoning

Improving probability selecting based weights for Satisfiability Problem

2020-07-30 · Huimin Fu, Yang Xu, Jun Liu, Guanfeng Wu 외

The Boolean Satisfiability problem (SAT) is important on artificial intelligence community and the impact of its solving on complex problems. Recently, great breakthroughs have been made respectively on stochastic local …

Variable Selection

Machine Learning Methods in Solving the Boolean Satisfiability Problem

2022-03-02 · Wenxuan Guo, Junchi Yan, Hui-Ling Zhen, Xijun Li 외

This paper reviews the recent literature on solving the Boolean satisfiability problem (SAT), an archetypal NP-complete problem, with the help of machine learning techniques. Despite the great success of modern SAT solve…

BIG-bench Machine Learning