Sparse solutions of linear Diophantine equations

We present structural results on solutions to the Diophantine system $A\mathit{y}=\mathit{b}$, $\mathit{y}\in {\mathbb{Z}}_{\ge 0}^t$ with the smallest number of non-zero entries. Our tools are algebraic and number theoretic in nature and include Siegel’s Lemma, generating functions, and commutative algebra. These results have some interesting consequences in discrete optimization.