LP Relaxation as a Lower Bound

Consider a minimization integer program (IP):

$$z^*_{IP} = \min\{\mathbf{c}^T\mathbf{x} : A\mathbf{x} \le \mathbf{b},\ \mathbf{x} \ge \mathbf{0},\ \mathbf{x} \in \mathbb{Z}^n\}.$$

Its LP relaxation drops the integrality constraints:

$$z^*_{LP} = \min\{\mathbf{c}^T\mathbf{x} : A\mathbf{x} \le \mathbf{b},\ \mathbf{x} \ge \mathbf{0}\}.$$

Every IP-feasible point is also LP-feasible, so the LP feasible region contains the IP feasible region. Minimizing the same objective over a larger set can only produce a smaller-or-equal optimum:

$$z^*_{LP} \le z^*_{IP}.$$

The LP relaxation optimum is therefore a lower bound on the IP optimum.

To illustrate, consider the IP $\min x$ subject to $x \ge 1.4$ and $x \in \mathbb{Z}$. The integer-feasible values are $\{2, 3, 4, \dots\}$, so $z^*_{IP} = 2$. Its LP relaxation $\min x$ subject to $x \ge 1.4$ admits any real $x \ge 1.4$, so $z^*_{LP} = 1.4$. Indeed $1.4 \le 2$, as guaranteed.