Title

Meta-Raps Approach For The 0-1 Multidimensional Knapsack Problem

Keywords

0-1 multidimensional Knapsack Problem; Greedy algorithm; Meta-heuristics; Optimization

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 achieves good results. © 2004 Elsevier Ltd. All rights reserved.

Publication Date

1-1-2005

Publication Title

Computers and Industrial Engineering

Volume

48

Issue

1 SPEC. ISS.

Number of Pages

83-96

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/j.cie.2004.02.008

Socpus ID

10844294197 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/10844294197

This document is currently not available here.

Share

COinS