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

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!

-
Counter example: $\sqrt{3}x-\sqrt{2}y=0$ (can write it as two $\geq$ inequalities). – polkjh Jan 30 '13 at 17:59
I think what we have here is (at least) two cases. If ${\bf b} = {\bf 0}$, then we can find counterexamples like polkjh's. If ${\bf b} > {\bf 0}$ then dexter04's argument works. That still leaves the situation where some of the entries in ${\bf b}$ are positive and some are $0$. – Mike Spivey Jan 30 '13 at 18:06
This counter example has the trivial (and only) solution $x=y=0$. Am I overlooking something? – mindriot Jan 31 '13 at 0:48
@mindriot: The equation $\sqrt{3}x - \sqrt{2}y = 0$ defines a line. So there are an infinite number of solutions, all of which other than $x = y = 0$ are non-integer. So I suppose it's not actually a counterexample, since it does include the integer solution $x = 0, y = 0$. – Mike Spivey Jan 31 '13 at 0:56
@MikeSpivey: yes, correct – I meant to say it's the only integer solution, thanks for clarifying. But like you said, it's not a counterexample. – mindriot Jan 31 '13 at 1:02

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.

-
+1. You need the additional restriction that c is strictly greater than ${\bf 0}$, though (which of course is forced if ${\bf b} > {\bf 0}$). Otherwise, you aren't guaranteed to get $A (k {\bf x}_0)$ large enough to compensate for $\delta {\bf 1}$ in all entries. – Mike Spivey Jan 30 '13 at 17:54
Looks great to me at a quick glance, I'll have to go over it more carefully (rusty math on my part and all). Thanks so far! – mindriot Jan 31 '13 at 0:55
I agree with @MikeSpivey. The question of individual $c_i=0$ is still open, but apart from that the proof works. I think the clue is that to compensate for $\delta$ in an entry where $c_i=0$, you would have to somehow choose $k$ so that the "critical" entries in $k{\bf x_0}$ are already integer. I'm not sure if that's even possible though... – mindriot Jan 31 '13 at 11:04