I have undertermined linear system with small number (< 30) variables. The possible solution for variables is integer from 0 to 3. How effeciently can I find all solutions? I tried bruteforcing, but that was slow.
Is it possible with some mathematical software (Gurobi, Cplex)?
I am ignorant of integer programming, so this answer could be naïve.
Did you exploit the linear equations when brute forcing ?
I mean, assuming $M$ equations in $N$ unknowns, where $M<N$, you can write your system of equations like
$$[A|A']\left[\frac X{X'}\right]=\left[B\right]$$ where $A$ is square $m\times m$, and solve partially as $$X=A^{-1}B-A^{-1}A'X'.$$
Then you can brute force on the independent unknowns ($X'$) and check the dependent ones, which will take $4^{N-M}$ SAXPY operations instead of $4^N$, a significant saving if $M$ is close to $N$.
In theory all computations should be made exactly using fractional arithmetic, but floating-point accuracy should be enough for a first screening of the solutions.