Projected Model Counting: Beyond Independent Support
Lists
Only you see this
Abstract
Given a system of constraints over a set X of variables, projected model counting asks us to count satisfying assignments of the constraint system projected on a subset $$\mathcal {P}$$ of X. A key idea used in modern projected counters is to first compute an independent support, say $$\mathcal {I}$$ , that is often a small subset of $$\mathcal {P}$$ , and to then count models projected on $$\mathcal {I}$$ instead of on $$\mathcal {P}$$ . While this has been effective in scaling performance of counters, the question of whether we can benefit by projecting on variables beyond $$\mathcal {P}$$ has not been explored. In this paper, we study this question and show that contrary to intuition, it can be beneficial to project on variables even beyond $$\mathcal {P}$$ . In several applications, a good upper bound of the projected model count often suffices. We show that in several such cases, we can identify a set of variables, called upper bound support (UBS), that is not necessarily a subset of $$\mathcal {P}$$ , and yet counting models projected on UBS guarantees an upper bound of the projected model count. Theoretically, a UBS can be exponentially smaller than the smallest independent support. Our experiments show that even otherwise, UBS-based projected counting can be faster than independent support-based projected counting, while yielding bounds of high quality. Based on extensive experiments, we find that UBS-based projected counting can solve many problem instances that are beyond the reach of a state-of-the-art independent support-based projected model counter.
BibTeX
@inproceedings{yang2022projected,
author = {Jiong Yang and Supratik Chakraborty and Kuldeep S. Meel},
title = {{Projected Model Counting: Beyond Independent Support}},
booktitle = {ATVA},
year = {2022},
doi = {10.1007/978-3-031-19992-9\_11},
}Loading related content...