Solution‐based versus attribute‐based tabu search for binary integer programming

Abstract Tabu search is one of the most commonly used local search‐based metaheuristics. A key component of the search is the tabu criterion, which controls whether it should be prohibited to make certain moves relative to the current solution. While attribute‐based tabu criteria have been dominant for decades, an alternative has received increased attention lately. Using a set of hash functions to map solutions onto hash values, a solution‐based tabu criterion has been used successfully, in particular for optimization problems involving binary variables. This paper compares the performance of solution‐based and attribute‐based tabu search on the general binary integer programming problem. According to computational experiments conducted on a sample of 160 benchmark instances, there is no statistically significant difference between the performances of solution‐based tabu search and attribute‐based tabu search.