The input consists of two integers $n\geq 2$ and $K\geq 2$, and a vector of positive integers $b$ of size $n$. We assume that $\sum_i b_i$ is a multiple of $K$.
The output is a matrix $A(n\times n)$ where each entry belongs to $\{0,1,...,K\}$ and where each column must sum to $K$.
We must have $Ax\geq b$ and $\sum_i x_i$ must be minimized. It is easy to see that the optimal value for $\sum_i x_i$ is $\frac{\sum_i b_i}{K}$, a corresponding matrix $A$ is for example the identity matrix multiplied by $K$ : $A=KI_n$.
My question is the following: for a given input, we know the optimal value of $\sum_i x_i$, but is there a matrix $A$ for which $\sum_i x_i$ is optimal and for which each component of $x$ is integer ?
Here is an example with $n=2$, $K=3$ and $b=(10\hspace{0.3cm}2)^T$. We have $\sum_i b_i=12$ which is a multiple of $K=3$.
As described above, an easy solution is: $$\begin{pmatrix}3 & 0 \\ 0 & 3\end{pmatrix}\begin{pmatrix}x_1 \\ x_2\end{pmatrix}\geq \begin{pmatrix}10 \\ 2\end{pmatrix},$$ it leads to $x_1=\frac{10}{3}$ and $x_2=\frac{2}{3}$. Now the question is: is there a matrix $A$ (with the constraints described above) such that $x_1+x_2=4$ where $x_1$ and $x_2$ are integers? It appears that it is yes in this case: $$\begin{pmatrix}2 & 3 \\ 1 & 0\end{pmatrix}\begin{pmatrix}x_1 \\ x_2\end{pmatrix}\geq \begin{pmatrix}10 \\ 2\end{pmatrix},$$ for which $x_1=2$ and $x_2=2$.
Up to now, I did not find any example where there is no integer solution. But is there a way to prove it ? Or is it not true ?
Thank you very much for your help.