The Knapsack-Problem With Disjoint Multiple-Choice Constraints
Abbreviated Journal Title
Nav. Res. Logist.
ALGORITHM; Operations Research & Management Science
In this article we consider the binary knapsack problem under disjoint multiple-choice constraints. We propose a two-stage algorithm based on Lagrangian relaxation. The first stage determines in polynomial time an optimal Lagrange multiplier value, which is then used within a branch-and-bound scheme to rank-order the solutions, leading to an optimal solution in a relatively low depth of search. The validity of the algorithm is established, a numerical example is included, and computational experience is described.
Naval Research Logistics
"The Knapsack-Problem With Disjoint Multiple-Choice Constraints" (1992). Faculty Bibliography 1990s. 391.