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