Proceedings

Decomposition Strategies to Count Integer Solutions over Linear Constraints

Cunjing Ge, Armin Biere

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 1389-1395.

https://doi.org/10.24963/ijcai.2021/192

Keywords

  • Constraints and SAT: SAT: Algorithms and Techniques
  • Constraints and SAT: Satisfiability Modulo Theories
  • Constraints and SAT: SAT: Solvers and Applications

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.

Cunjing Ge, and Armin Biere. 2021. Decomposition Strategies to Count Integer Solutions over Linear Constraints. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 1389–1395. https://doi.org/10.24963/ijcai.2021/192
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards