Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
2  
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
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
1  
+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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.