I'd be interested to see how a Genetic algorithm with carefully chosen mutation/recombination operators would suit this problem.

Mutations could be flips and random swaps. Recombination would be combining chunks of already partially optimised solutions (breeding).

Genetic algorithms do suffer a cost of having to keep a population of solutions in memory so it would be interesting to see how the end results compares in performance to annealing.