Simulated Annealing Algorithm for the Multiple Choice Multidimensional Knapsack Problem

원문 초록

The multiple choice multidimensional knapsack problem (MCMK) is a harder version of the 0/1 knapsack problem, and is ever more complex than the 0/1 multidimensional knapsack problem. In MCMK, there are several groups of items. The objective is to maximize the value (profit) by choosing exactly 1 item from each group such that all the constraints are satisfied. It is difficult and NP-hard even to find a solution that does not violate all constraints. In this work, we present a simulated annealing based algorithm with open source C++ code to find good solutions to the multidimensional multiple choice knapsack problem. In all of the benchmark instances we used, the algorithm is able to find optimum (or close) solutions, thereby proving that the algorithm is suitable for solving larger instances for which optimal solutions are unknown.