I like the Column Generation idea. Not a big fan of SA and LNS as you often can't really tell the relative quality of the solutions. I've often pushed for a different, simpler model form when the larger model isn't solvable in the usual ways. Running out of memory in CPLEX or Gurobi is a sign you need to reformulate more than anything else. Of course, that requires having people capable of formulating and evaluating math programming formulations. Turns out there aren't so many of those. Surprised me at first, but I guess I shouldn't be surprised. The real trick in optimization is coming up with the right formulation.