We obtain a polynomial-time algorithm that, given input
, where
,
, with
nonsingular
and
,
finds a nonnegative integer solution to the system
or determines that no such solution exists, provided that
is located sufficiently “deep” in the cone generated by the columns of
. This
result improves on some of the previously known conditions that guarantee
polynomial-time solvability of linear Diophantine problems.