The bi-objective quadratic multiple knapsack problem: Model and heuristics

The single objective quadratic multiple knapsack problem (QMKP) is a useful model to formulate a number of practical problems. However, it is not suitable for situations where more than one objective needs to be considered. In this paper, we extend the single objective QMKP to the bi-objective case such that we simultaneously maximize the total profit of the items packed into the knapsacks and the ’makespan’ (the gain of the least profit knapsack). Given the imposing computational challenge, we propose a hybrid two-stage (HTS) algorithm to approximate the Pareto front of the bi-objective QMKP. HTS combines two different and complementary search methods — scalarizing memetic search (first stage) and Pareto local search (second stage). Experimental assessments on a set of 60 problem instances show that HTS dominates a standard multi-objective evolutionary algorithm (NSGA II), and two simplified variants of HTS. We also present a comparison with two state-of-the-art algorithms for the single objective QMKP to assess the quality of the extreme solutions of the approximated Pareto front.