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. Iter...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2014-02, Vol.232 (3), p.454-463
Main Authors: García-Martínez, C., Rodriguez, F.J., Lozano, M.
Format: Article
Language:English
Subjects:
Algorithms
Combinatorial analysis
Destruction
Destruction mechanism
Effectiveness studies
Flexibility
Greedy algorithms
Heuristic
Iterated greedy search
Iterative methods
Knapsack problem
Operational research
Quadratic multiple knapsack problem
Searching
Tabu search
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•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.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2013.07.035