[sirwhinesalot]

There's an interesting tool called LocalSolver that uses local search methods by default for everything but if it detects a "decidable" class of problem it can also use fancier algorithms capable of returning a global optima, likely running both in parallel.

Sadly I haven't had a chance to try it.