Approximate Integer Solution Counts over Linear Arithmetic Constraints
Abstract
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 (epsilon, delta)-bound. Experiments on extensive benchmarks show that our algorithm could solve polytopes with dozens of dimensions, which significantly outperforms state-of-the-art counters.
Cite
Text
Ge. "Approximate Integer Solution Counts over Linear Arithmetic Constraints." AAAI Conference on Artificial Intelligence, 2024. doi:10.1609/AAAI.V38I8.28640Markdown
[Ge. "Approximate Integer Solution Counts over Linear Arithmetic Constraints." AAAI Conference on Artificial Intelligence, 2024.](https://mlanthology.org/aaai/2024/ge2024aaai-approximate/) doi:10.1609/AAAI.V38I8.28640BibTeX
@inproceedings{ge2024aaai-approximate,
title = {{Approximate Integer Solution Counts over Linear Arithmetic Constraints}},
author = {Ge, Cunjing},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2024},
pages = {8022-8029},
doi = {10.1609/AAAI.V38I8.28640},
url = {https://mlanthology.org/aaai/2024/ge2024aaai-approximate/}
}