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

Chaitr S. Hiremath and Raymond R. Hill

International Journal of Operational Research, 2007, vol. 2, issue 4, 495-512

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. (search for similar items in EconPapers)
Date: 2007
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.inderscience.com/link.php?id=14176 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijores:v:2:y:2007:i:4:p:495-512

Access Statistics for this article

More articles in International Journal of Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().