Title: New greedy heuristics for the Multiple-choice Multi-dimensional Knapsack Problem

Authors: Chaitr S. Hiremath, Raymond R. Hill

Addresses: Wright State University, 207 Russ Engineering Center, 3640 Col. Glenn Highway, Dayton, OH 45435, USA. ' Wright State University, 207 Russ Engineering Center, 3640 Col. Glenn Highway, Dayton, OH 45435, USA

Abstract: This paper examines the Multiple-choice Multi-dimensional Knapsack Problem (MMKP) – a more complex variant of the classic knapsack problem (KP). We survey existing algorithms for the variants of the KP and critically examine existing test problems for the MMKP. We present an empirical study of sample legacy solution approaches compared to two new systematically-developed greedy heuristics for the MMKP. We extend our testing to include a new systematically-generated test problem set. Characteristics of all the problem sets are compared and used to explain the empirical performance results obtained and demonstrate the superiority of our greedy heuristic approach.

Keywords: optimisation; greedy heuristics; knapsack problem; empirical testing; operational research.

DOI: 10.1504/IJOR.2007.014176

International Journal of Operational Research, 2007 Vol.2 No.4, pp.495 - 512

Published online: 24 Jun 2007 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article