Tabu search is a popular metaheuristic. The idea of tabu search in its simplest form is to first, make the lowest cost move at each stage in the search, and, second, to accept cost degrading moves. This means that in a local minimum, tabu search will move out, since it can accept cost degrading moves. However, unless prevented, it could immediately fall back to the local minimum it left by making the opposite if such an opposite move exists (as is common) and such a move is now the best one that can be made (which is also common).

To counteract this cycling effect, tabu search employs various mechanisms, the typical one, and that implemented in Solver, being the tabu list. This list holds information on the solutions recently visited and forbids the search from moving back to a solution which is the same as (or shares some features or attributes with) one it has recently visited. The length of the list is usually important to the performance of the metaheuristic. Typically this metaheuristic performs better than simulated annealing.