If you google this one, you're going to get sickened by all the plaigiarization in the world going on. Everyone is stuck on the obvious case of $n = 2$. I want for $n$ variables (general linear).
So given an equation of the form
$$ D = Ax + By + \dots + Cz \tag{1} $$
in finitely many variables $n$, where $A, B, C, \dots, D \in \Bbb{Z}$ or in particular $\Bbb{N}$, how does one write down the general, parameterized solution?
Next question, given the general solution can we minimize $x + y + \dots + z$ over the set of solutions, all in polynomial time?
That is, can we do all of the above given $(1)$ in polynomial time and space complexity?
All solutions lay in $\Bbb{N}^n$, and in fact there are quite small bounds attached to each variable, such as $x \in \{0, 2\}$ for smallish instances of my input problem. However combined this can naively be approximately $2^n$ or more points to try. That is not polynomial time.
I am going to define my notations a bit more clearly and try to make myself clearer. I consider the equation $B=\sum_{i=1}^n{A_ix_i}$, where the $x_i$ (and only them) are unknowns in $\mathbb{Z}^n$.
I am denoting, for any vector $z \in \mathbb{Z}^n$, $\|z\|_1=\sum_{k=1}^n{|z_k|}$ and $\|z\|_0=|\{k,\,z_k \neq 0\}$, and $d(z)$ the gcd of the entries of $z$.
$G_n$ is the group of invertible $n \times n$ matrices with integer entries, such that their reciprocals have also integer entries.
A transvection is a $n \times n$ matrix $M$ with entries in $\mathbb{Z}$, all diagonal entries equal to $1$, and exactly one other nonzero entry. It is always in $G_n$.
The first part is to check that for all $M \in G_n$, $z \in \mathbb{Z}^n$, $d(Mz)=d(z)$. This is because $d(z)$ “clearly” divides $d(Mz)$, and $z=M^{-1}(Mz)$ so the inverse divisibility also holds.
The key lemma is as follows: let $a \in \mathbb{Z}^n$. If $\|a\|_0 \geq 2$, then there exists a transvection $M \in G_n$ such that $\|Ma\|_1 < \|a\|_1$.
Proof: there exists indices $i \neq j$ and an integer $k$ such that $0 < a_i-ka_j < |a_i|$. So take for $M$ the only transvection such that $M_{i,j}=-k$.
So we can construct (each of the constructions in “linear” time) vectors $A^0=A=(A_1, \ldots, A_n), A^1, \ldots, A^p$ and transvections $M_1, \ldots, M_p$, such that $M_iA^{i-1}=A^i$, and $\|A^i\|_1$ decreases, and $\|A^p\|=1$.
Thus, $p \leq \|A\|_1/d(A)$ (ie the procedure must stop).
Since $d(A^p)=d(A)$ and $\|A^p\|=1$, it can be found (in linear time) a matrix $N \in G_n$ such that $NA^p=(d(A),0,0,\ldots,0)$.
Note that for any matrix $M$ and any transvection $P$ (of which one already knows the location of the nondiagonal nonzero entry), $MP$ can be computed by a single column operation in $M$, ie by in linear time.
So $M=NM_p\ldots M_1$ can be computed in $O(np)=O(n\|A\|_1/d(A))$ time such that $(d(A),0,\ldots,0)=MA$.
As a consequence, let $z \in \mathbb{Z}^n$, write $z=\sum_{i=1}^n{\alpha_iL_i(M)}$, where $L_i(M)$ is the $i$-th line of $M$.
Then since $A \cdot L_i(M)=L_i(MA)=0$ if $i \geq 2$ and $d(A)$ if $i=1$, so $\sum_{i=1}^n{z_iA_i}=\alpha_1d(A)$.
Thus $\{z,\,B=\sum_{i=1}^n{A_iz_i}\}$ is freely generated by $B/d(A)L_1(M)$ (if $d(A)$ does not divide $B$ the set is instead empty) and all $L_k(M)$, $k \geq 2$.
I am not sure how much it helps you to find solutions in non-negative integers though.