Exact Solution Algorithms for Multi-dimensional Multiple-choice Knapsack Problems
Farhad Ghassemi-Tari *
Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran.
Hamed Hendizadeh
Department of Mechanical and Manufacturing Engineering, Faculty of Engineering, University of Manitoba, Winnipeg, Manitoba, Canada.
Gary L. Hogg
Department of Industrial Engineering, Arizona State University, USA.
*Author to whom correspondence should be addressed.
Abstract
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.
Keywords: Multiple-dimensional multiple-choice knapsack, Branch and bound, Exact solution approach, Selective branching mechanisms