Calculating the upper bound of the multiple-choice knapsack problem

Authors
Nakagawa, Y Kitao, M Tsuji, M Teraoka, Y
Citation
Y. Nakagawa et al., Calculating the upper bound of the multiple-choice knapsack problem, ELEC C JP 3, 84(7), 2001, pp. 22-27
Citations number
9
Categorie Soggetti
Eletrical & Eletronics Engineeing
Journal title
ELECTRONICS AND COMMUNICATIONS IN JAPAN PART III-FUNDAMENTAL ELECTRONIC SCIENCE
ISSN journal
10420967 → ACNP
Volume
84
Issue
7
Year of publication
2001
Pages
22 - 27
Database
ISI
SICI code
1042-0967(2001)84:7<22:CTUBOT>2.0.ZU;2-X
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 propos ed a branchand-bound algorithm for solving the Multiple-Choice Knapsack Pro blem, 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 metho ds. (C) 2001 Scripta Technica.