I want to write an efficient program to the determine if the following equation is solvable.
The equation and the constraints look like this: $$\begin{align} &\sum_{i=1}^{n}a_ix_i=0\quad(\forall i,a_i\in\mathbb{Z}\backslash0,x_i\in\mathbb{Z})\\ &\forall i,|x_i|\le M_i\quad(M_i\in\mathbb{Z}^+)\\ &\sum_{i=1}^{n}|x_i|>0 \end{align}$$
After some searching, I found it's somehow related to Integer Linear Programming, which is generally NP-hard. Anyway I hope somebody knows an efficient algorithm for this particular problem and please give me some help.
Thanks
A dynamic programming approach can work well if the $a_i$ and $M_i$ are not too large. Let $T(v,j) = true$ if there is a solution to $\sum_{i=1}^j a_i x_i = v$ with $x_1, \ldots, x_j$ integers, not all $0$, with $|x_i| \le M_i$, otherwise $T(v,j) = false$.
Of course it is $false$ if $|v| > \sum_{i=1}^j |a_i| M_i$. Moreover, $T(v,j)$ is $true$ iff $v = x a_j$ with $|x| \in \{1,\ldots, M_j\}$ or some $T(v - a_j x, j-1)$ with $|x| \in \{0, \ldots, M_j\}$. Thus we can compute the $T(v,j)$ recursively in pseudo-polynomial time. Your problem has a solution iff $T(0, n)$ is $true$; if it is, by tracing backwards through the computed $T(v,j)$ we can construct a solution.