Two-stage solution-based tabu search for the multidemand multidimensional knapsack problem

The multidemand multidimensional knapsack problem (MDMKP) is a significant generalization of the popular multidimensional knapsack problem with relevant applications. In this work we investigate for the first time how solution-based tabu search can be used to solve this computationally challenging problem. For this purpose, we propose a two-stage search algorithm, where the first stage aims to locate a promising hyperplane within the whole search space and the second stage tries to find improved solutions by exploring the reduced subspace defined by the hyperplane. Computational experiments on 156 benchmark instances commonly used in the literature show that the proposed algorithm competes favorably with the state-of-the-art results. We analyze several key components of the algorithm to highlight their impacts on the performance of the algorithm. (C) 2018 Elsevier B.V. All rights reserved.