Does branch-and-bound always achieve a globally optimal solution?

Question

I read from some references that the branch-and-bound algorithm will always obtain a globally optimal solution (not suboptimal, not local, or not approximate solution). Is that true? How to prove that?

Answer 1

The idea of branch and bound is almost close to brute force search.

We keep splitting the search space, and work on the subproblems. The bounding part of the algorithm stop us from exploring a branch only if it is proven to not consist of the optimal solution.

Since we do not discard any potential global optimal, we will find one if it exists.

Answer 2

To add to the above answer, we will always get the global optimum (not taking into account the time needed to get there).

The idea is that we try and find an integer feasible solution and search the tree if and only if the current node's fractional solution has a potential to improve the current best integer solution.

If it can't yield a better integer solution (current node's fractional solution is worse than the best integer solution), there is no need to continue exploring past the current node, as adding boundary constraints will necessary worsen the solution.

If it can yield a better integer solution (if the current node's fractional solution is better than the current best integer solution), we continue branching until we either find a better integer solution, the problem becomes infeasible or the fractional solution can no longer improve on the current best integer solution.

This means that we can think of it as looking at all of the possible solutions which have the potential to improve on the current solution.

As other commenters noted, we can think of it as a smart brute force algorithm.