Decomposition Strategies to Count Integer Solutions over Linear Constraints
Abstract
Counting integer solutions of linear constraints has found interesting applications in various fields. It is equivalent to the problem of counting integer points inside a polytope. However, state-of-the-art algorithms for this problem become too slow for even a modest number of variables. In this paper, we propose new decomposition techniques which target both the elimination of variables as well as inequalities using structural properties of counting problems. Experiments on extensive benchmarks show that our algorithm improves the performance of state-of-the-art counting algorithms, while the overhead is usually negligible compared to the running time of integer counting.
Cite
Text
Ge and Biere. "Decomposition Strategies to Count Integer Solutions over Linear Constraints." International Joint Conference on Artificial Intelligence, 2021. doi:10.24963/IJCAI.2021/192Markdown
[Ge and Biere. "Decomposition Strategies to Count Integer Solutions over Linear Constraints." International Joint Conference on Artificial Intelligence, 2021.](https://mlanthology.org/ijcai/2021/ge2021ijcai-decomposition/) doi:10.24963/IJCAI.2021/192BibTeX
@inproceedings{ge2021ijcai-decomposition,
title = {{Decomposition Strategies to Count Integer Solutions over Linear Constraints}},
author = {Ge, Cunjing and Biere, Armin},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2021},
pages = {1389-1395},
doi = {10.24963/IJCAI.2021/192},
url = {https://mlanthology.org/ijcai/2021/ge2021ijcai-decomposition/}
}