Take Action
Research Details
The Multiple-Choice Knapsack Problem, Operations Research
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.
Type
Article
Author(s)
Prabhakant Sinha, Andris Zoltners
Date Published
1979
Citations
Sinha, Prabhakant, and Andris Zoltners. 1979. The Multiple-Choice Knapsack Problem. Operations Research. 27(3): 503-515.