Generation Methods for Multidimensional Knapsack Problems and their Implications

Abstract

Although there are a variety of heuristics developed and applied to the variants of the binary knapsack problem, the testing of these heuristics are based on poorly defined test problems. This paper reviews the various types of knapsack problems, considers how test problems have been generated and depicts via empirical results the implications of using poorly formed test problems for empirical testing.

Keywords

• multiple dimensional knapsack
• problem generation
• knapsack problems