Hybridization of tabu search with feasible and infeasible local searches for the quadratic multiple knapsack problem

Jin Qin, Xianhao Xu, Qinghua Wu, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

18 Citations (Scopus)

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.
Original languageEnglish
Article number3834
Pages (from-to)199-214
Number of pages16
JournalComputers and Operations Research
Volume66
DOIs
Publication statusPublished - 1 Feb 2016

Keywords

  • Infeasible local search
  • Tabu search
  • The quadratic multiple knapsack problem

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research

Cite this