The knapsack problem with disjoint multiple‐choice constraints

Vijay Aggarwal, Narsingh Deo and Dilip Sarkar

Naval Research Logistics (NRL), 1992, vol. 39, issue 2, 213-227

Abstract: 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.

Date: 1992
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/nav.3220390206

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:wly:navres:v:39:y:1992:i:2:p:213-227

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().