I'm struggling with the following exercise.
We consider an integer programming problem:
$$\min \;\; \mathbf{c} \cdot \mathbf{x}\\
\text{s.t. } A\mathbf{x} \geq \mathbf{b} \\
\mathbf{x} \geq \mathbf{0} \\
\mathbf{x} \in \mathbb{Z}^n$$
where the entries of $A, \mathbf{b}, \mathbf{c}$ are integers. We assume that its linear programming relaxation has optimal cost equal to $-\infty$ and that the integer linear program is feasible. I need to show that the optimal cost of the integer programming problem is $-\infty$.
Intuitively that seems quite clear to me, but I'm not able to prove it.
Also, will the statement still hold if the entries of $A, \mathbf{b}$ and $\mathbf{c}$ are allowed to be non-integer? (I guess there could be some problem with irrational numbers)
Best Answer
First of all, if the coefficients are not integer, then not necessarily. Consider
$$ \min x \quad\text{ subject to }\quad x+\sqrt{2}y=0 $$
With $(x,y)\in\mathbb{R}^2$, obviously the minimum is $-\infty$. However, with $(x,y)\in\mathbb{Z}^2$, the only solution is $x=y=0$ so the minimum is $0$.
If $A$, $b$, and $c$ are integer, and $A$ is totally unimodular, then the relaxation is equivalent to the integer program so the answer is yes: unboundedness in the relaxation implies unboundedness of the integer program.
If not, then things get much more complicated. First, feasibility of the integer program seems quite important. For example, consider
$$\min x\quad\text{ subject to }3x+3y=2$$
In $\mathbb{R}^2$ clearly the solution is $-\infty$, however this has no integer solutions as there's no way to create 2 from a multiple of 3, so this system is infeasible in $\mathbb{Z}^2$. This example shows that the assumption of feasibility of the integer program is not implied by feasibility of the relaxed program.
So, let us suppose there is some integer solution $x$, as in the question. Since the relaxed program is unbounded, and since all coefficients $A$ and $b$ are integer, there is a direction $$\delta\in\mathbb{Q}^n$$ of unboundedness described by rational coefficients, because such direction can be constructed from the final simplex table that shows the unboundedness, and this table will only contain rational values. More specifically, for every $\lambda\in\mathbb{R}_{\ge 0}$, we have that $$A(x+\lambda\delta)\ge b$$ Because we assumed that the relaxed program has solution $-\infty$, we also know that $c^T\delta<0$, since the objective function must go to $-\infty$ as $\lambda$ goes to $+\infty$ . However, because $\delta$ contains only rational values, the set $$\{x+\lambda\delta\colon\lambda\in\mathbb{R}_{\ge 0}\}$$ must contain infinitely many integer points, for instance those of the form $$\{x+n\lambda^*\delta\colon n\in\mathbb{N}\}$$ where $\lambda^*$ is the smallest integer such that $\lambda^*\delta\in\mathbb{Z}^n$. Such $\lambda^*$ exists because $\delta$ has only rational values.
Note that I did not use the the fact that $c$ is integer: apparently that condition can be relaxed.