I'm searching for an integer solution to an arbitrary set of linear equations with binary coefficients. It is given that the rank of the Matrix is not maximal. The right hand side is the 0-vector.
So let $A \in \{0,1\}^{(d+k)\cdot (d+1)}$ with last column fixed to 1: $A_{i,d+1}=1\forall i\in \{1,..,d+k\}$, with $k \in \mathbb{N} \cup\{0\}$
Let $x\in \mathbb{Z}^{d+1}$ and $r = (0,...,0)^t \in \mathbb{N}^{d+k}$.
It is given that $rank(A) =d$ and there are no conflicting linear equations, thus there are infinitively many solutions.
I now want to search only for non-trivial integer solutions of $ A \cdot x =r$, preferably, the integers should be small.
Let's put that in the way that $x^* = argmin_x (max_i |x_i|)$ s.t. $Ax=r$ and $x\neq 0$. If it's easier for the task, the use of maximum-norm is not necessary, but the requirement that the integers of the solution should be near 0 (in the common sense, i.e. all above 10 would be odd to my kind of problem), is non-optional.
Are there fast/efficient algorithms to achieve this?