Premium
The knapsack problem with disjoint multiple‐choice constraints
Author(s) -
Aggarwal Vijay,
Deo Narsingh,
Sarkar Dilip
Publication year - 1992
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.3220390206
Subject(s) - knapsack problem , lagrangian relaxation , lagrange multiplier , continuous knapsack problem , mathematics , disjoint sets , mathematical optimization , polynomial time approximation scheme , change making problem , relaxation (psychology) , rank (graph theory) , combinatorics , psychology , social psychology
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.