Education, Science, Technology, Innovation and Life
Open Access
Sign In

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

All published work is licensed under a Creative Commons Attribution 4.0 International License.

Copyright © 2016 - 2031 Clausius Scientific Press Inc. All Rights Reserved.