← Search

The Multiple-Choice Knapsack Problem

Prabhakant Sinha¹; Andris A. Zoltners²

¹ University of Georgia, Athens, Georgia · ² Northwestern University, Evanston, Illinois

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.

DOI

10.1287/opre.27.3.503

Volume

27 (3)

Pages

503-515

Language

en

Export

BibTeX

Sources

crossref