Many strategies are available, when one wants to search a solution space for some feasible solution. The only one we have out ruled so far, is exhaustive search.
Several strategies where considered:
Both simulated annealing and tabu search rely somewhat on the fact that once a variable has been altered, we can be fairly sure, that next time we alter that variable, it will influence the result in nearly the same way. This is not at all the fact for our problem. The generation of fill-ins completely spoil that property. Placing one row/column in some position will have completely different impacts on our result, depending on the position of all other rows/columns.
From the simple analysis above, I decided to focus my efforts on branch and bound search. Early in the project, tabu search was implemented to some extent. But it was rather unsuccessful, even compared to the likewise very early implementation of branch and bound I had running. Therefore, I sticked with branch and bound, and decided to only work with the other two, if they suddenly became interesting due to some change of (my understanding of) the properties of the problem. That never occurred.