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

    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