A stitch in time…

This blog post from the excellent complexity blog Godel’s Lost Letter is on the theory behind branch and bound search. One of my favourite things about this sort of analysis is how it it can eliminate, with mathematical certainty, hours and hours of programming effort. Consider this statement:

There is an issue of being odd or even, which matters but not hugely, since pruning the bottom layer is not so valuable.

I have spent many hours working on problems that might fall into the “matters, but is not so valuable” category. A few hours of analysis might well have saved me a lot of trouble.