Please use this identifier to cite or link to this item:
Title: Hybridization of tabu search with feasible and infeasible local searches for the quadratic multiple knapsack problem
Authors: Qin, J
Xu, X
Wu, Q
Cheng, TCE 
Keywords: Infeasible local search
Tabu search
The quadratic multiple knapsack problem
Issue Date: 2016
Publisher: Pergamon Press
Source: Computers and operations research, 2016, v. 66, 3834, p. 199-214 How to cite?
Journal: Computers and operations research 
Abstract: The quadratic multiple knapsack problem (QMKP) concerns assigning a set of objects, which interact among themselves through paired profit values, to a set of capacity-constrained knapsacks such that the overall profit of the objects included in the knapsacks is maximized and the total weight of the objects in each knapsack does not exceed the capacity of the knapsack. In this paper we present a highly effective tabu search (TS) approach for QMKP that incorporates a hybridization scheme combining both feasible and infeasible local searches. The feasible local search focuses its search on the most relevant feasible solutions, while the infeasible local search explores a large search space composed of both feasible and infeasible solutions, and employs several tailored move selection rules to keep the infeasible solutions close to the feasible regions located in promising areas. Extensive computational results on a set of 60 benchmark instances in the literature illustrate that the new TS approach compares very favorably with the current state-of-the-art solution methods for QMKP. In particular, the TS approach finds improved best solutions for ten instances. We also analyze the hybridization scheme in the TS approach to ascertain its effect on the performance of the solution method.
ISSN: 0305-0548
EISSN: 1873-765X
DOI: 10.1016/j.cor.2015.08.002
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record


Last Week
Last month
Citations as of Feb 2, 2019


Last Week
Last month
Citations as of Feb 15, 2019

Page view(s)

Last Week
Last month
Citations as of Feb 17, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.