| Article ID: | iaor20072081 |
| Country: | United Kingdom |
| Volume: | 33 |
| Issue: | 5 |
| Start Page Number: | 1259 |
| End Page Number: | 1273 |
| Publication Date: | May 2006 |
| Journal: | Computers and Operations Research |
| Authors: | Akbar Md Mostofa, Rahman M. Sohel, Kaykobad M., Manning E.G., Shoja G.C. |
| Keywords: | heuristics |
This paper presents a heuristic to solve the Multidimensional Multiple-choice Knapsack Problem (MMKP), a variant of the classical 0–1 Knapsack Problem. We apply a transformation technique to map the multidimensional resource consumption to single dimension. Convex hulls are constructed to reduce the search space to find the near-optimal solution of the MMKP. We present the computational complexity of solving the MMKP using this approach. A comparative analysis of different heuristics for solving the MMKP has been presented based on the experimental results.