Solving a system of linear diophantine equations with lower and upper bounds on the variables

We develop an algorithm for solving a system of diophantine equations with lower and upper bounds on the variables. The algorithm is based on lattice basis reduction. It first rinds a short vector satisfying the system of dio phantine equations, and a set of Vectors belonging to the null-space of the constraint matrix. Due to basis reduction, all these vectors are relativel y short. The next step is to branch on linear combinations of the null-spac e vectors, which either yields a vector that satisfies the bound constraint s or provides a proof that no such Vector exists. The research was motivate d by the need for solving constrained diophantine equations as subproblems when designing integrated circuits for video signal processing. Our algorit hm is tested with good results on real-life data, and on instances from the literature.