THE KNAPSACK-PROBLEM WITH DISJOINT MULTIPLE-CHOICE CONSTRAINTS

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.