- 【Updated on May 12, 2025】 Integration of CiNii Dissertations and CiNii Books into CiNii Research
- Trial version of CiNii Research Automatic Translation feature is available on CiNii Labs
- Suspension and deletion of data provided by Nikkei BP
- Regarding the recording of “Research Data” and “Evidence Data”
THE MULTIPLE-CHOICE KNAPSACK PROBLEM
-
- Ibaraki Toshihide
- Department of Applied Mathematics and Physics, Faculty of Engineering Kyoto University
-
- Hasegawa Toshiharu
- Department of Applied Mathematics and Physics, Faculty of Engineering Kyoto University
-
- Teranaka Katsumi
- Yokosuka Electrical Communication Laboratory. N.T.T.
-
- Iwase Jiro
- IBM Japan, Ltd.
Bibliographic Information
- Other Title
-
- 多重選択ナップザック問題
Search this article
Description
This paper treats the multiple-choice (continuous) knapsack problem P: maximize Σ^^n__<i=1> Σ^^<m_i__<j=1>c_<ij>x_<ij>subject to (1) Σ^^n__<i=1> Σ^^<m_i__<j=1>c_<ij>x_<ij>⩽ b, (2) 0⩽ x_<ij>⩽ 1,i = 1,2 ,...,n,j=1,2,.... m_i and (3) at most one of x _<i1> , x _<i2>,..., x _<im_i> is positive for i = 1, 2,..., n, where n, m_i are positive integers ancl a_<i1>, c_<i1>, b are nonnegative real numbers. Two approximate algorithms and an exact branch-and-bound algorithm are proposed, by making use of the property that the LP relaxation of P provides considerably accurate upper and lower bounds of the optimal value of P. Although the multiple-choice knapsack problem is known to be NP-complete, computation results are quite encouraging. For example, approximate solutions withing 0.001% of the optimal values are obtained in less than one second (on FACOM 230/60) for problems with n = 1000 and m_i = 2, which are randomly generated from the uniform distribut[on. Exact optimal solutions of these problems with n = 500 and m_i = 2 are also obtainedin less than 0.2 seconds (on FACOM M190).
Journal
-
- Journal of the Operations Research Society of Japan
-
Journal of the Operations Research Society of Japan 21 (1), 59-95, 1978
The Operations Research Society of Japan
- Tweet
Details 詳細情報について
-
- CRID
- 1390282679085381504
-
- NII Article ID
- 110001184006
-
- ISSN
- 21888299
- 04534514
-
- Text Lang
- en
-
- Data Source
-
- JaLC
- Crossref
- CiNii Articles
- OpenAIRE
-
- Abstract License Flag
- Disallowed