A hybrid evolutionary search for the generalized quadratic multiple knapsack problem

Knapsack problems are useful models that can formulate many real-life applications. The generalized quadratic multiple knapsack problem (GQMKP) extends the well-known quadratic multiple knapsack problem by taking into account setups and knapsack preference of the items. In this study, an efficient hybrid evolutionary search algorithm (HESA) is proposed to tackle GQMKP, which relies on a knapsack-based crossover operator to generate new offspring solutions, and an adaptive feasible and infeasible tabu search to improve new offspring solutions. Other new features of HESA include a dedicated strategy to ensure a diversified and high-quality initial population, and a streamlining technique to speed up the evaluations of candidate solutions. The experiments on two sets of 96 benchmark instances as well as one large-scale real-life instance show that the proposed algorithm outperforms the state-of-the-art algorithms from the literature. In particular, HESA finds 44 improved best-known solutions (new lower bounds) (for more than 45% cases). The key components of the algorithm are studied to assess their effects on the algorithm’s performance.