---
title: "Decomposition Strategies to Count Integer Solutions over Linear Constraints"
authors:
  - "Cunjing Ge"
  - "Armin Biere"
doi: "10.24963/ijcai.2021/192"
url: "https://ijcai.org/proceedings/2021/192"
pdf: "https://ijcai.org/proceedings/2021/0192.pdf"
venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"
year: 2021
pages: "1389-1395"
track: "Main Track"
keywords:
  - "Constraints and SAT: SAT: Algorithms and Techniques"
  - "Constraints and SAT: Satisfiability Modulo Theories"
  - "Constraints and SAT: SAT: Solvers and Applications"
---

# Decomposition Strategies to Count Integer Solutions over Linear Constraints

Cunjing Ge, Armin Biere

*Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence*, pages 1389-1395. DOI: [10.24963/ijcai.2021/192](https://doi.org/10.24963/ijcai.2021/192)

## 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.