How to determine if a integer linear equation with contraints is solvable? 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.
