Optimization of Approximate Model Counting Method Based on Bivariate Decomposition
Download as PDF
DOI: 10.23977/meimie.2019.43077
Author(s)
Xuan Zhou, Bin Zhang, Yankun Tu, Shuaiqi Wang and Sihan Jia
Corresponding Author
Xuan Zhou
ABSTRACT
This paper proposes an improved method for approximate model counting based on bivariate optimization. With the development of hash functions, scalable approximate model counting algorithms that can solve tens of thousands of variables in recent years have been proposed, improved and applied. However, in practical applications, there are still a large number of laws for the actual input data of different problems, and there is a lot of optimization space. This paper proposes an input variable optimization algorithm based on bivariate optimization for approximate model counting. It optimizes the structure of a large number of bivariate and univariate inputs in practical problems, and successfully improves the calculation time of the most approximate model counting problems without losing accuracy.
KEYWORDS
Approximate model counting, bivariate decomposition, #SAT