[zodiac]

I'm pretty sure cutting-plane methods for IP don't strictly require "tree search" (of course, they still require super-polynomial time to solve IP problems)

https://en.wikipedia.org/wiki/Cutting-plane_method