Approximating Integer Solution Counting via Space Quantification for Linear Constraints
Abstract
Solution counting or solution space quantification (means volume computation and volume estimation) for linear constraints (LCs) has found interesting applications in various fields. Experimental data shows that integer solution counting is usually more expensive than quantifying volume of solution space while their output values are close. So it is helpful to approximate the number of integer solutions by the volume if the error is acceptable. In this paper, we present and prove a bound of such error for LCs. It is the first bound that can be used to approximate the integer solution counts. Based on this result, an approximate integer solution counting method for LCs is proposed. Experiments show that our approach is over 20x faster than the state-of-the-art integer solution counters. Moreover, such advantage increases with the problem scale.
Cite
Text
Ge et al. "Approximating Integer Solution Counting via Space Quantification for Linear Constraints." International Joint Conference on Artificial Intelligence, 2019. doi:10.24963/IJCAI.2019/235Markdown
[Ge et al. "Approximating Integer Solution Counting via Space Quantification for Linear Constraints." International Joint Conference on Artificial Intelligence, 2019.](https://mlanthology.org/ijcai/2019/ge2019ijcai-approximating/) doi:10.24963/IJCAI.2019/235BibTeX
@inproceedings{ge2019ijcai-approximating,
title = {{Approximating Integer Solution Counting via Space Quantification for Linear Constraints}},
author = {Ge, Cunjing and Ma, Feifei and Ma, Xutong and Zhang, Fan and Huang, Pei and Zhang, Jian},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2019},
pages = {1697-1703},
doi = {10.24963/IJCAI.2019/235},
url = {https://mlanthology.org/ijcai/2019/ge2019ijcai-approximating/}
}