Variable neighbourhood decomposition search with bounding for multidimensional knapsack problem

Abstract

In this paper we propose a new heuristic for solving multidimensional knapsack problem, based on the variable neighbourhood decomposition search principle. The set of neighbourhoods is generated by exploiting information obtained from a series of relaxations. In each iteration, we add new constraints to the problem in order to produce a sequence of lower and upper bounds around the optimal value, with the goal to reduce the gap between them. General-purpose CPLEX MIP solver is used as a black box for solving subproblems generated during the search process. With this approach, we have managed to obtain promising results on a set of large scale multidimensional knapsack problem instances. The results are comparable with the current state-of-the-art techniques for solving multidimensional knapsack problem.