Centrality Heuristics for Exact Model Counting

Show full item record



Permalink

http://hdl.handle.net/10138/311783

Citation

Bliem , B & Järvisalo , M 2020 , Centrality Heuristics for Exact Model Counting . in IEEE 31st International Conference on Tools with Artificial Intelligence (ICTAI 2019) . Proceedings-International Conference on Tools With Artificial Intelligence , IEEE Computer Society , pp. 59-63 , 31st International Conference on Tools with Artificial Intelligence (ICTAI 2019) , Portland, OR , United States , 04/11/2019 . https://doi.org/10.1109/ICTAI.2019.00017

Title: Centrality Heuristics for Exact Model Counting
Author: Bliem, Bernhard; Järvisalo, Matti
Contributor: University of Helsinki, Department of Computer Science
University of Helsinki, Department of Computer Science
Publisher: IEEE Computer Society
Date: 2020-02-13
Language: eng
Number of pages: 5
Belongs to series: IEEE 31st International Conference on Tools with Artificial Intelligence (ICTAI 2019)
Belongs to series: Proceedings-International Conference on Tools With Artificial Intelligence
ISBN: 978-1-7281-3799-5
978-1-7281-3798-8
URI: http://hdl.handle.net/10138/311783
Abstract: Model counting is the archetypical #P-complete problem consisting of determining the number of satisfying truth assignments of a given propositional formula. In this short paper, we empirically investigate the potential of employing graph centrality measures as a basis of search heuristics in the context of exact model counting. In particular, we integrate centrality-based heuristics into the search-based exact model counter sharpSAT. Our experiments show that employing centrality information significantly improves the empirical performance of sharpSAT, and also allows for simplifying the search heuristics compared to the current default heuristics of the model counter. In particular, we show that the VSIDS heuristic, which is an integral search heuristic employed in essentially all state-of-the-art conflict-driven clause learning Boolean satisfiability solvers, appears to be of very limited use in the context of model counting.
Subject: 113 Computer and information sciences
exact model counting
#SAT
search heuristics
graph centrality
betweenness centrality
SEARCH
Rights:


Files in this item

Total number of downloads: Loading...

Files Size Format View
main.pdf 255.6Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record