I feel most of those big search problems could be solved much easier and quicker with some form of annealing/tree search/dynamic or greedy algorithms with results very close to the theoretical linear optimum
But of course those won't get you a thesis ;)
In this case I could prove it was the globally optimal solution.
But this was only possible of course due to the internal structure of the problem: it was in effect a simpler problem hiding within a linear integer program. Standard solvers couldn’t find this structure, but it was possible to do by hand.
It might also be possible to add problem-specific cuts/heurstics to the solver so that it can solve it fast.