A particular ILP where the existence of a relaxed solution implies the existence of an integer solution

Question

This question emerged from a discussion on my previous question Determining quickly whether this Integer Linear Program has any solution at all, which I would like to elaborate separately.

I am trying to determine whether a solution exists for $$ \begin{aligned} A\mathbf{x} &\geq \mathbf{b} &\text{where}\quad \mathbf{x} &\in \mathbb{Z}^m,\ \mathbf{x}\geq\mathbf{0},\ \\ && \mathbf{b} &\in \mathbb{R}^n,\ \mathbf{b}\geq\mathbf{0},\ \\ && A&\in \mathbb{R}^{n\times m}\ . \end{aligned} $$ I postulate that in this particular case, if a solution exists for the relaxed constraint $\mathbf{x} \in \mathbb{R}^m,\ \mathbf{x}\geq\mathbf{0}$, an integer solution always exists as well.

The proof would go somewhat like this: $A\mathbf{x}$ spans a pointed convex cone $C_a$ from the origin. The criterion $\mathbf{y} \geq \mathbf{b}$ implies a cone $C_b$ originating at $\mathbf{b}$, with the particular trait that if the two cones intersect, every ray in $C_a$ which intersects $C_b$ will intersect exactly one side of $C_b$, i.e. it will enter $C_b$ but never leave it. This should, in turn, imply that there must exist an $\mathbf{x} \in \mathbb{Z}^m,\ \mathbf{x}\geq\mathbf{0}$ so that $A\mathbf{x} \geq \mathbf{b}$.

Obviously that is not a proof, and anything but formal. But maybe someone could enlighten me on how such a formal proof could be constructed – or maybe, in case I'm altogether wrong, provide a counterexample? Thanks in advance!

Answer 1

Suppose you have a feasible solution in the reals, $\mathbf{x}_0\in \mathbb{R}^m$ such that $\mathbf{Ax}_0 = \mathbf{c \ge b}$, where by $\ge$, I mean every element of $\mathbf{c}$ is $\ge$ its corresponding element in $\mathbf{b}$.

Now, note that for every positive real $k>1$, $\mathbf{A}(k\mathbf{x}_0) = k\mathbf{c} \ge \mathbf{b}$.

Suppose you round up a real solution $\mathbf{x} $to an integer one $\mathbf{x_i}$. So, $\mathbf{x_i = x + \epsilon, \quad x_i \in } \mathbb{Z}^m$.

Also, $0\le \epsilon_i < 1, i = 1,2,\ldots m$

Now, $\mathbf{Ax_i = Ax + A\epsilon}$.

Let $\mathbf{e = A\epsilon}$. Then, $e_i = \sum_{j=1}^{n}a_{ij}\epsilon_j$. So, $e_i \ge -\sum_{j=1}^{n}|a_{ij}|$ with equality occuring in case all entries of $\mathbf{A}$ are negative.

Let $$\delta = \min_i{e_i} \le 0$$ Then, $$\mathbf{e\ge}\delta \mathbf{1}$$

So, $\mathbf{Ax_i = Ax +e \ge Ax }+ \delta \mathbf{1}$

Now, note that $\delta $ is a property of $\mathbf{A}$, and is fixed. So, by choosing a large enough $k$, setting $\mathbf{x} = k\mathbf{x_0}$ and rounding $\mathbf{x}$ to its next highest integer, a feasible integer solution s.t. $\mathbf{Ax_i\ge b}$ can be always obtained.