LP Relaxation Bound for Branch-and-Bound

Let $x \in \mathbb{Z}^n_{\ge 0}$ denote the integer feasible set and $x \in \mathbb{R}^n_{\ge 0}$ the (larger) LP-relaxed feasible set of the same constraints $Ax \le b$. Because dropping the integrality requirement only removes constraints, every integer-feasible point is also LP-feasible, so the integer feasible set is a subset of the LP-relaxed feasible set.

Since both problems maximize the same linear objective $c^T x$ and the integer program's feasible set is contained in the LP relaxation's feasible set, the best value achievable over the smaller set cannot exceed the best value achievable over the larger set. Hence the LP relaxation optimum is an upper bound on the ILP optimum.

Branch-and-bound builds a search tree by picking a variable with a fractional value in the current LP-relaxed solution and creating two child subproblems that add $x_1 \le 1$ or $x_1 \ge 2$ respectively; every integer-feasible point satisfies exactly one of these two conditions, so no integer solution is ever lost by this split, and repeating the split keeps partitioning the space without gaps.

At each node, solving the LP relaxation of that subproblem gives an upper bound for every integer solution still reachable below it, by the same argument as above applied to the smaller constraint set. If this bound is no larger than the value of the best integer solution found anywhere in the tree so far, no descendant of this node can improve on the current best, so the whole subtree may be pruned while still guaranteeing the true optimum is found elsewhere in the tree.