簡単そうに見えて難しい問題

研究に使うためにとある問題を解くプログラムを組んでいるのですが、「整数成分のベクトルと、同じサイズの整数成分のベクトルの有限集合が与えられたとき、前者に後者の整数係数一次結合を加えて全ての成分を非負にできるか判定する」問題*1って何か良い解き方はあるんでしょうか。
手元の組合せ最適化のテキストを信じるならば一般の場合の簡単な解法はなさそうですし・・・うーむ。

*1:専門用語を使うと、整数行列と整数ベクトルで定義される多面体が格子点を含むかどうか判定する問題