Skip to Main content Skip to Navigation
Journal articles

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
Document type :
Journal articles
Complete list of metadata

https://hal-uphf.archives-ouvertes.fr/hal-03623239
Contributor : Mylène Delrue Connect in order to contact the contributor
Submitted on : Tuesday, March 29, 2022 - 3:38:58 PM
Last modification on : Friday, August 5, 2022 - 3:44:16 PM

Identifiers

Collections

Citation

Raïd Mansi, Cláudio Alves, J.M. Valério de Carvalho, Said Hanafi. A hybrid heuristic for the multiple choice multidimensional knapsack problem. Engineering Optimization, Taylor & Francis, 2013, 45 (8), pp.983-1004. ⟨10.1080/0305215X.2012.717072⟩. ⟨hal-03623239⟩

Share

Metrics

Record views

4