Approximate Integer Solution Counts over Linear Arithmetic Constraints
This addresses a computational bottleneck in fields requiring lattice point counting, offering a faster approximate solution for high-dimensional polytopes.
The paper tackles the problem of counting integer solutions of linear constraints, which is slow for many variables, by proposing a new random-walk sampling method that approximates lattice counts with proven bounds, achieving significant performance improvements on benchmarks with dozens of dimensions.
Counting integer solutions of linear constraints has found interesting applications in various fields. It is equivalent to the problem of counting lattice 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 a new framework to approximate the lattice counts inside a polytope with a new random-walk sampling method. The counts computed by our approach has been proved approximately bounded by a $(ε, δ)$-bound. Experiments on extensive benchmarks show that our algorithm could solve polytopes with dozens of dimensions, which significantly outperforms state-of-the-art counters.