Meta-RaPS approach for the 0-1 Multidimensional Knapsack Problem
Abbreviated Journal Title
Comput. Ind. Eng.
meta-heuristics; optimization; greedy algorithm; 0-1 Multidimensional; Knapsack Problem; PROGRAMMING-PROBLEMS; TABU SEARCH; ALGORITHM; Computer Science, Interdisciplinary Applications; Engineering, ; Industrial
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 for 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 achievers good results. (C) 2004 Elsevier Ltd. All rights reserved.
Computers & Industrial Engineering
Article; Proceedings Paper
"Meta-RaPS approach for the 0-1 Multidimensional Knapsack Problem" (2005). Faculty Bibliography 2000s. 5492.