Decomposition Strategies to Count Integer Solutions over Linear Constraints

Cunjing Ge, Armin BiereIJCAI 2021 · DOI

Counting the number of integer points inside a polytope—a shape defined by linear inequalities—is a fundamental problem in computer science with critical applications in probabilistic program analysis, software verification, and automated planning. However, this task is computationally #P-hard. While existing tools like BARVINOK are mathematically sophisticated, their performance typically degrades exponentially as the number of variables increases, often hitting a "wall" once a problem exceeds 15 variables.

This paper introduces INTCOUNT, a tool designed to break this performance barrier by using novel decomposition strategies to simplify complex, high-dimensional problems into smaller, independent sub-problems.

Decomposition Strategies

The core contribution of INTCOUNT is a two-pronged strategy that simplifies the Linear Constraint Graph (LCG), where nodes represent variables and edges represent their co-occurrence in a constraint. By forcing independence between variables, the tool can leverage a "divide and conquer" approach.

  1. Column Elimination: Inspired by Boolean SAT solving, this method selects a variable and enumerates its possible integer values. Fixing a variable to a constant often causes dependencies between other variables to vanish, splitting the problem into independent components.
  2. Row Elimination: This is the paper’s most novel contribution. Instead of fixing a variable, the algorithm "splits" a complex constraint (a row in the matrix) into smaller pieces by introducing auxiliary variables. This process can decouple original variables into entirely separate sub-problems.
Figure 5: An illustration of Row Elimination. By removing or splitting a specific constraint (row), the dependency graph is decomposed into independent sub-problems.

Experimental Evaluation

The authors evaluated INTCOUNT using over 6,000 benchmarks, including random polytopes and real-world application instances from program analysis and temporal planning. The tool uses a heuristic search to identify the most effective rows or columns to eliminate, ensuring the overhead for finding a decomposition remains negligible (averaging only 0.0247 seconds).

Key Results

  • Superior Scaling: INTCOUNT significantly outperformed state-of-the-art engines like BARVINOK and propositional model counters such as CACHET and GANAK. It solved a higher volume of cases within the one-hour timeout period.
  • Problem Compression: For decomposable problems, the average number of variables per sub-problem dropped from approximately 14 to just 3, drastically reducing the computational burden on the underlying counting engine.
  • Real-world Impact: In application-specific benchmarks, INTCOUNT proved particularly effective on complex cases that previously caused other tools to time out, extending the practical reach of integer counting in software verification.
Figure 6: Cumulative solved cases over time. INTCOUNT (top blue line) consistently solves more instances faster than competing tools like BARVINOK, Cachet, and GANAK.

Conclusion and Future Work

INTCOUNT demonstrates that even if a decomposition requires solving thousands of sub-problems, the exponential nature of integer counting makes solving many tiny problems orders of magnitude faster than solving one medium-sized problem. Future work will focus on improving cost estimation heuristics to determine when decomposition is most beneficial and handling variables with extremely large domains, which currently pose a challenge for enumeration-based strategies.

Summary updated

BibTeX
@inproceedings{ge2021decomposition,
  author = {Cunjing Ge and Armin Biere},
  title = {{Decomposition Strategies to Count Integer Solutions over Linear Constraints}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/192},
}
Figure