The Multiple-Choice Knapsack Problem
- 1 June 1979
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 27 (3) , 503-515
- https://doi.org/10.1287/opre.27.3.503
Abstract
The multiple-choice knapsack problem is defined as a binary knapsack problem with the addition of disjoint multiple-choice constraints. The strength of the branch-and-bound algorithm we present for this problem resides with the quick solution of the linear programming relaxation and its efficient, subsequent reoptimization as a result of branching. An implemented version of this algorithm has performed well on a large set of test problems. We cite computational results as well as a comparison with a previously reported algorithm. Several useful applications of the multiple-choice knapsack problem are also suggested.Keywords
This publication has 0 references indexed in Scilit: