Calculating the upper bound of the Multiple-Choice Knapsack Problem.

An upper bound or a lower bound of the Multiple-Choice Knapsack Problem can be calculated by solving LP relaxation. In 1979, Sinha and Zoltners proposed a branch-and-bound algorithm for solving the Multiple-Choice Knapsack Problem, and provided a method to obtain the strict upper bound. In this paper, we propose a new calculation method to obtain a stricter upper bound than the upper bound of Sinha–Zoltners and compare the results of the two methods. © 2001 Scripta Technica, Electron Comm Jpn Pt 3, 84(7): 22–27, 2001 [ABSTRACT FROM AUTHOR]