Nonnegative integer solutions, when nonnegative solutions exist and integer solutions exist

Question

I have a set of vectors $v_i$, $1\leq i\leq N$ for some $N$ over the real numbers that are not linearly independent. We will express them as natural-number-valued functions from some integer interval $[n]\to\mathbb{N}$. I also have a specific other vector $v:[n]\to\mathbb{N}$. I know the following:

1. $$v_i(j)\leq v(j)\mbox{ for all }i,j$$
2. There exist $a_i\in\mathbb{Z}$ such that $$\sum_i a_iv_i(j)=v(j)$$ for all $j$.
3. There exist $b_i\geq 0$ in $\mathbb{R}$ such that $$\sum_i b_iv_i(j)=v(j)$$ for all $j$.

What other conditions can we add to ensure that there exist $c_i\in\mathbb{N}$ such that $$\sum_i c_iv_i(j)=v(j)$$ for all $j$?

My problem is that I have a series of integer programming problems that are not all feasible to solve. However, the problems are feasible to solve when we relax to regular LP. There are some special properties of the vectors in the problem that could conceivably imply that nonnegative integer solutions exist if nonnegative real solutions exist, which would eliminate the need to run the integer programming. However, this may not be the case, and the integer programming may be necessary after all.

Answer 1

This is not a full answer, but I thought I'd share some things that came to mind.

1. Let $a_1,\dots,a_N\in \mathbb{N}$ be relatively prime, then, famously, $\forall n> F(a_1,\dots, a_N)$, where $F$ denotes the Frobenius number of $a_1,\dots,a_N$, there exist $m_1,\dots,m_n\in \mathbb{N}$ s.t. $$n=\sum_{i=1}^{N}m_ia_i$$

In the case where $gcd(a_1,\dots,a_N)=d\neq0$, then the same applies for $n=0[d]$ and $n>d*F(a_1/d,\dots,a_N/d)$.

Unfortunately, this is neither a sufficient nor necessary condition for your problem, since all the $m_i$ would be dependent if we were to apply the previous reasoning component-wise. However, it might be otherwise useful to show that such a combination cannot exist.

2. We can simplify point 3. by noticing that the $b_i$ must be rational. Indeed, if they weren't, consider the field extension $\mathbb{Q}(b_i)$: it is a finite dimensional vector field over $\mathbb{Q}$ with basis $\{1,b_i\}$ and thus the sum:

$$\sum_i v_i(j)b_i\in \mathbb{N},\quad \forall j\in [n]$$

would imply $v_i(j)=0$. Adjacently, recall that Gaussian elimination only uses coefficients in the smallest field containing the values of the vectors.

3. I had a hunch that we could assume the $v_i$ independent (and we certainly can as far as 3. is concerned), but I was wrong, since it clashes with 1.

For example:

$$v_1=\begin{pmatrix} 6\\2\end{pmatrix}\quad v_2=\begin{pmatrix} 0\\3\end{pmatrix}\quad v_3=\frac{2}{3}v_1+\frac{2}{9}v_2=\begin{pmatrix} 4\\2\end{pmatrix}\quad v=\begin{pmatrix} 10\\5\end{pmatrix}$$

You can check that there are no $c_i$ in this case and also no $a_i$ for any two vectors alone, but we can write $v=3v_1+v_2-2v_3$.

Finally, I'd like to add that although this is an interesting problem, I do not believe the question as stated is clear since you gave an example yourself that it is not true, and so I believe you should edit it to clarify what exactly an answer to your question would look like.