Sparse solutions of linear diophantine equations

We present structural results on solutions to the Diophantine system Ay = b, y ∈ Z t ≥0 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