The Multiple-Choice Knapsack Problem

Prabhakant Sinha and Andris A. Zoltners
Additional contact information
Prabhakant Sinha: University of Georgia, Athens, Georgia
Andris A. Zoltners: Northwestern University, Evanston, Illinois

Operations Research, 1979, vol. 27, issue 3, 503-515

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.

Date: 1979
References: Add references at CitEc
Citations: View citations in EconPapers (41)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.27.3.503 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:27:y:1979:i:3:p:503-515

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().