Title

Meta-RaPS approach for the 0-1 Multidimensional Knapsack Problem

Authors

Authors

R. J. Moraga; G. W. DePuy;G. E. Whitehouse

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

Comput. Ind. Eng.

Keywords

meta-heuristics; optimization; greedy algorithm; 0-1 Multidimensional; Knapsack Problem; PROGRAMMING-PROBLEMS; TABU SEARCH; ALGORITHM; Computer Science, Interdisciplinary Applications; Engineering, ; Industrial

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

Journal Title

Computers & Industrial Engineering

Volume

48

Issue/Number

1

Publication Date

1-1-2005

Document Type

Article; Proceedings Paper

Language

English

First Page

83

Last Page

96

WOS Identifier

WOS:000226391000007

ISSN

0360-8352

Share

COinS