Exact Solution Algorithms for Multi-dimensional Multiple-choice Knapsack Problems

We propose a first depth dual approach branch and bound (B&B) routine for solving the general form of multi-dimensional multiple-choice knapsack problems (MMKPs).We call this approach a discriminatory branch and bound method. This name is chosen due to the selection of a node for further branching based on a discriminatory criterion. Three selection mechanisms are developed and are incorporated in an algorithmic procedure to develop three algorithms. An extensive computational experiment is performed, to compare the number of nodes enumerated by the proposed algorithms against the traditional B&B. The results revealed that all the proposed algorithms lead to a considerable node enumeration reduction.