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

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

0.00 Avg rating0 Votes
Article ID: iaor20082002
Country: United Kingdom
Volume: 2
Issue: 4
Start Page Number: 495
End Page Number: 512
Publication Date: Jun 2007
Journal: International Journal of Operational Research
Authors: ,
Keywords: heuristics
Abstract:

This paper examines the Multiple-choice Multi-dimensional Knapsack Problem (MMKP) – a more complex variant of the classic knapsack problem (KP). We survey exist 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.

Reviews

Required fields are marked *. Your email address will not be published.