Heuristic algorithms for the multiple-choice multidimensional knapsack problem

Heuristic algorithms for the multiple-choice multidimensional knapsack problem

0.00 Avg rating0 Votes
Article ID: iaor20062261
Country: United Kingdom
Volume: 55
Issue: 12
Start Page Number: 1323
End Page Number: 1332
Publication Date: Dec 2004
Journal: Journal of the Operational Research Society
Authors: , ,
Keywords: programming: integer
Abstract:

In this paper, we propose several heuristics for approximately solving the multiple-choice multidimensional knapsack problem (noted MMKP), an NP-Hard combinatorial optimization problem. The first algorithm is a constructive approach used especially for constructing an initial feasible solution for the problem. The second approach is applied in order to improve the quality of the initial solution. Finally, we introduce the main algorithm, which starts by applying the first approach and tries to produce a better solution to the MMKP. The last approach can be viewed as a two-stage procedure: (i) the first stage is applied in order to penalize a chosen feasible solution and, (ii) the second stage is used in order to normalize and to improve the solution given by the first stage. The performance of the proposed approaches has been evaluated based on problem instances extracted from the literature. Encouraging results have been obtained.

Reviews

Required fields are marked *. Your email address will not be published.