A new exact algorithm to solve the Multiple-Choice Multidimensional Knapsack Problem: The Utility Sorted Branch and Bound Algorithm

This paper offers an exact algorithm for one of the most complex members of the Knapsack Problem family: The Multiple-choice Multidimensional Knapsack Problem (MMKP). Based on a literature survey, only a few exact algorithms exist for the MMKP. The proposed algorithm excludes ranges of the possible solution space through systematic variations of ranked elements by utility sorting. Based on logical rules, successor nodes of a feasible node cannot include the optimal solution. Besides a literature survey as well as a detailed description of the algorithm and the test design, the results of a computational study on 11,160 instances are presented. The efficiency of the algorithm depends on the number of classes, elements per class, number of restrictions, and the degree of restrictiveness. Using the distribution of a search quotient shows the relative number of examined solutions being investigated. Testing against a brute-force algorithm reveals that all problem instances could be solved exactly while reducing the number of node enumerations. Furthermore, the structure of the algorithm allows its usage on other members of the knapsack problem family.