BnB example: TSP
Consider the Travelling Salesperson Problem
Branch and Bound might use depth-first search
Cost so far is sum of costs of chosen edges
Bound might be cost of following minimum spanning tree of remaining nodes
- MST: tree connected to all nodes of min cost among all such trees
- all routes have to visit all remaining nodes
- can’t possibly beat cost of MST
Bounds often much more sophisticated
- e.g. using mathematical programming optimisations