Meta-RaPS approach for the 0–1 multidimensional knapsack problem

Meta-RaPS approach for the 0–1 multidimensional knapsack problem

0.00 Avg rating0 Votes
Article ID: iaor20051944
Country: Netherlands
Volume: 48
Issue: 1
Start Page Number: 83
End Page Number: 96
Publication Date: Jan 2005
Journal: Computers & Industrial Engineering
Authors: , ,
Keywords: heuristics
Abstract:

A promising solution approach called Meta-RaPS is presented for the 0–1 Multidimensional Knapsack Problem (0–1 MKP). Meta-RaPS constructs feasible solutions at each iteration through the utilization of a priority rule used in a randomized fashion. Four different greedy priority rules are implemented within Meta-RaPS and compared. These rules differ in the way the corresponding pseudo-utility ratios ranking variables are computed. In addition, two simple local search techniques within Meta-RaPS' improvement stage are implemented. The Meta-RaPS approach is tested on several established test sets, and the solution values are compared to both the optimal values and the results of other 0–1 MKP solution techniques. The Meta-RaPS approach outperforms many other solution methodologies in terms of differences from the optimal value and number of optimal solutions obtained. The advantage of the Meta-RaPS approach is that it is easy to understand and easy to implement, and it achieves good results.

Reviews

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