Papers › Simulated Annealing Algorithm for the Multiple Choice Multidimensional Knapsack Problem
Simulated Annealing Algorithm for the Multiple Choice Multidimensional Knapsack Problem
Shalin Shah
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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections