Algorithm counts integer program solutions faster with simpler steps
A Simple Algorithm for Counting Solutions to Integer Programs
Computational Complexity
Summary
Counting the number of ways to solve certain math problems with whole numbers can be very slow and complicated. The authors present a simpler method that speeds up this counting task for a specific type of problem. Their method works well by using fewer arithmetic steps while still handling problems with many variables and constraints. This improvement builds on earlier, more complex algorithms.
What this means in practice
- •For operations research analysts: Count feasible scheduling or resource allocation scenarios efficiently when modeling constraints with integer programs.
- •For cryptography engineers: Estimate the number of integer solutions in lattice-based models relevant for cryptographic scheme analysis.
A theory result. No direct application yet.
Authors
Daniel Dadush, Anita Dürr, Thekla Hamm, Jonas Schmidt, Karol Węgrzycki
Abstract
We consider the problem of counting solutions to integer linear programming problems of the form $\{x \in \mathbb{Z}^n_{\geq 0} : Ax = b\}$ where $A \in \{-Δ,\ldots,Δ\}^{m \times n}$ and $b \in \mathbb{Z}^m$. We present an algorithm that counts solutions with $(nΔ)^{m + o(1)}\! \cdot \log\lVert b\rVert$ arithmetic operations. This simplifies the algorithm of Gribanov and Malyshev, who considered the problem for the more general setting in which $A$ is $Δ$-modular.