A hybrid heuristic for the multiple choice multidimensional knapsack problem
Raid Mansi, Cláudio Alves, José Valério de Carvalho, Said Hanafi
Submitted, 2011

ABSTRACT
In this paper, we describe a new solution approach for the multiple choice multidimensional knapsack problem. 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. In this paper, we explore a new hybrid heuristic that embeds several new procedures. Our heuristic 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 bound for the optimal solution value. In this paper, we explore a new strategy for defining the reduced problems. We propose a new family of cuts and a reformulation procedure that is used at each iteration to improve the performance of the heuristic. We report on an extensive set of computational experiments for benchmark instances from the literature and for a large set of hard instances generated randomly. Our results show that our approach outperforms other state-of-the-art methods described so far, providing the best known solution for a significant number of benchmark instances.

BIBTEX ENTRY
@article{MansiAlvesCarvalhoHanafiMMKP11,
author = {Ra{\"i}d Mansi and Cl{\'a}udio Alves and Jos{\'e} Val{\'e}rio de Carvalho and Fran\c{c}ois Clautiaux and Sa{\"i}d Hanafi},
title = {A hybrid heuristic for the multiple choice multidimensional knapsack problem},
year = {2011},
note = {submitted} }