Calculating the upper bound of the Multiple-Choice Knapsack Problem

✍ Scribed by Yuji Nakagawa; Masachika Kitao; Mitsuhiro Tsuji; Yoshinobu Teraoka

• Publisher: John Wiley and Sons
• Year: 2001
• Tongue: English
• Weight: 179 KB
• Volume: 84
• Category: Article
• ISSN: 1042-0967
• DOI: 10.1002/ecjc.1018

✦ Synopsis

Abstract

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