Examples are TSP, shortest path, and the dynamic programming solution to the paragraph formatting problem on the exam.
In all these examples, a line of search can be abandoned when a partial solution (the beginning of a path or the beginning of a paragraph) is already so bad that no matter how it gets completed it cannot end up better than some solution we already know.
Thus branch-and-bound is a way to avoid searching in those parts of the solution space where there is no chance of finding an optimal solution.
Last edited (or copied to this place) at 7:30 AM, Saturday, November 11, 1995.