The Multiple-Choice Knapsack Problem, Operations Research
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.
Prabhakant Sinha, Andris Zoltners
Sinha, Prabhakant, and Andris Zoltners. 1979. The Multiple-Choice Knapsack Problem. Operations Research. 27(3): 503-515.