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

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.