Decomposition Strategies to Count Integer Solutions over Linear Constraints
Decomposition Strategies to Count Integer Solutions over Linear Constraints
Cunjing Ge, Armin Biere
Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence
Main Track. Pages 1389-1395.
https://doi.org/10.24963/ijcai.2021/192
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.
Keywords:
Constraints and SAT: SAT: Algorithms and Techniques
Constraints and SAT: SAT: Solvers and Applications
Constraints and SAT: Satisfiability Modulo Theories