First we should be all be clear on the definition of a "relaxation":
Suppose you have a problem (P) and its relaxation (R).
(R) is a relaxation of (P), with the same decision variable $x$ iff the feasible set of (R) contains that of (P) (that is, $X_{(P)} \subseteq X_{(R)}$), and over the feasible set of (R), the objective function dominates that of (P) (That is, $f_{(R)}(x) \leq f_{(P)}(x)\quad\forall x\in X$).
So it should clearly follow from these two conditions that (for a minimisation problem), a linear relaxation must always give a lower bound of its corresponding IP.
The IP is bounded by some polyhedron with the additional constraint that only the integral points are feasible. The LR relaxation is the same polyhedron where all points are feasible. Therefore, the first condition is satisfied as the set of all points in a polyhedron must logically include all integral points in the same polyhedron.
The second condition is also met as the objective function of (R) is equal at all points to that of (P).
If you think about it visually, there are two possible cases for an integer program (IP) and its corresponding linear relaxation (LR):
- You solve (LR) and all variables are integral. Either (IP) has the integrality property (where the optimal solution of the corresponding (LR) will always be integral, such as with LPs with totally unimodular matrices), or you were lucky and the optimal solution of (IP) touches the edge of the polyhedron that bounds the feasible region.
- You solve (LR) and some or all variables are not integral. You can be certain that (for a minimisation problem), the optimal value to the corresponding (IP) must be at least the optimal solution to (LR), since the set of feasible points of (IP) is contained inside that of (LR), and because the function values of (IP) at any arbitrary point is at least as great as that of (LR) at the same point.
Suppose you have some problem (P) with a set of feasible points $X$. (These points need not necessarily be integral, just any finite set of points). If the feasible region of (P) is $conv(X)$ (the convex hull of $X$), then the optimal solution to the relaxation or $x\in X$ (where we consider ALL points inside the feasible region, not just those in $X$) will be the optimal solution.