So, we solve a relaxation of the integer program. We get a solution. It is not integer. So we create branches where in each new branch, we form appropriate bounds to rule out the non-integer solution. We repeat.
Okay. ... why does this converge? My book doesn't mention it at all, just gives an example that converges. I want to know why this converges. Who is to say that I will never, ever reach an integer solution, I just keep getting worse and worse non-integer solutions.
Branch and bound converges because, in the worst case, it reduces to enumerating all of the feasible solutions.
For example, suppose we have an IP with only two variables $x_1$ and $x_2$. Suppose we solve the LP relaxation, and obtain a solution with $x_1=1.5$. Then we branch, by creating two new subproblems with $x_1\leqslant1$ and $x_1\geqslant2$. Now we solve the first ($x_1\leqslant1$ subproblem), and obtain a solution with $x_1=0.5$. So we add two more subproblems, with the constraints $x_1\leqslant0$ and $x_1\geqslant1$ (see picture below).
Repeating in this way, we eventually fix the value of $x_2$ as well. Repeating in this way over and over, we eventually list all of the possible solutions.
But what if there are infinitely many feasible solutions?
This is where the bounding comes in. As soon as we find an integer feasible solution, we automatically prune every integer feasible solution which produces an equal or worse objective value. As long as the problem has a finite optimal solution, the bounding process will reduce the infinite search space to a finite one. The proper choice of branching variables, and the order in which you solve the subproblems can greatly affect how long this process takes.
