A hybrid heuristic for the multiple choice multidimensional knapsack problem

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...

Full description

Saved in:
Bibliographic Details
Published in:Engineering optimization 2013-08, Vol.45 (8), p.983-1004
Main Authors: Mansi, Raïd, Alves, Cláudio, Valério de Carvalho, J. M., Hanafi, Saïd
Format: Article
Language:English
Subjects:
Algorithms
Benchmarking
Computer Science
Heuristic
hybrid heuristics
integer linear programming
Knapsack problem
Linear programming
Mathematical analysis
Mathematical models
Mathematical problems
multiple choice knapsack problem
Optimization
relaxations
Strategy
Very large scale
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0305-215X
1029-0273
DOI:10.1080/0305215X.2012.717072