A hybrid heuristic for the multiple choice multidimensional knapsack problem

Abstract

In this article, a new solution approach for the multiple choice multidimensional knapsack problem is described. The problem is a variant of the multidimensional knapsack problem where items are divided into classes, and exactly one item per class has to be chosen. Both problems are NP-hard. However, the multiple choice multidimensional knapsack problem appears to be more difficult to solve in part because of its choice constraints. Many real applications lead to very large scale multiple choice multidimensional knapsack problems that can hardly be addressed using exact algorithms. A new hybrid heuristic is proposed that embeds several new procedures for this problem. The approach is based on the resolution of linear programming relaxations of the problem and reduced problems that are obtained by fixing some variables of the problem. The solutions of these problems are used to update the global lower and upper bounds for the optimal solution value. A new strategy for defining the reduced problems is explored, together with a new family of cuts and a reformulation procedure that is used at each iteration to improve the performance of the heuristic. An extensive set of computational experiments is reported for benchmark instances from the literature and for a large set of hard instances generated randomly. The results show that the approach outperforms other state-of-the-art methods described so far, providing the best known solution for a significant number of benchmark instances.

Keywords:

• hybrid heuristics
• multiple choice knapsack problem
• integer linear programming
• relaxations

Acknowledgements

This work was partially supported by the Portuguese Science and Technology Foundation through postdoctoral grant SFRH/BPD/64766/2009 for Raïd Mansi, by the Portuguese Science and Technology Foundation through project PTDC/EGE-GES/116676/2010 and by the Algoritmi Research Center for Cláudio Alves and José Valério de Carvalho, and by the International Campus on Safety and Intermodality in Transportation, the Nord-Pas-de-Calais Region, the European Community, the Regional Delegation for Research and Technology, the Ministry of Higher Education and Research, and the National Center for Scientific Research for Saïd Hanafi.