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

Qun Zhao, Xintao Wang, Menghui Yang
10/26/2023
cs.AI

No confident code implementation found for this paper.

Abstract

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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Inductive Learning of Declarative Domain-Specific Heuristics for ASP

80% match2023

Machine Learning for SAT: Restricted Heuristics and New Graph Representations

80% match2023

Certified MaxSAT Preprocessing

79% match2024

An AlphaZero-Inspired Approach to Solving Search Problems

78% match2022

Advancing Stochastic 3-SAT Solvers by Dissipating Oversatisfied Constraints

78% match2025

General Method for Solving Four Types of SAT Problems

78% match2023

Cite this paper

@article{zhao2023boolean,
  title  = {New Boolean satisfiability problem heuristic strategy: Minimal Positive Negative Product Strategy},
  author = {Qun Zhao and Xintao Wang and Menghui Yang},
  year   = {2023},
  eprint = {2310.18370},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2310.18370v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2310.18370.svg)](https://codeofpaper.com/paper/2310.18370)

Discussion