Tabu-enhanced iterated greedy algorithm: A case study in the quadratic multiple knapsack problem

• Iterated greedy algorithms are tested on the quadratic multiple knapsack problem.
• A memory-enhanced destruction mechanism for iterated greedy is proposed.
• Problem-knowledge exploitation is identified in the iterated greedy proposal.
• Tabu-enhanced iterated greedy solves the problem effectively.

Iterated greedy search is a simple and effective metaheuristic for combinatorial problems. Its flexibility enables the incorporation of components from other metaheuristics with the aim of obtaining effective and powerful hybrid approaches. We propose a tabu-enhanced destruction mechanism for iterated greedy search that records the last removed objects and avoids removing them again in subsequent iterations. The aim is to provide a more diversified and successful search process with regards to the standard destruction mechanism, which selects the solution components for removal completely at random.We have considered the quadratic multiple knapsack problem as the application domain, for which we also propose a novel local search procedure, and have developed experiments in order to assess the benefits of the proposal. The results show that the tabu-enhanced iterated greedy approach, in conjunction with the new local search operator, effectively exploits the problem-knowledge associated with the requirements of the problem considered, attaining competitive results with regard to the corresponding state-of-the-art algorithms.