Enumerating the image of an integer matrix applied to a lattice

44 Views Asked by At

Let $A\in\mathbb{Z}^{n \times m}$ and $x\in \mathbb{Z}^m$. Also suppose we are given $l,u\in\mathbb{Z}^m$. I would like to efficiently enumerate $$\{Ax \,|\, l_i \le x_i \le u_i \text{ for all } i\}$$

The subscript $i$ refers to the $i^\text{th}$ element of the vector.

$A$ is not necessarily of full rank, so the problem is nontrivial.

Is there a simple algorithm for this problem? Even just a reference would be appreciated.

Thanks.