A heuristic solution procedure for the multiconstraint zero‐one knapsack problem

Hasan Pirkul

Naval Research Logistics (NRL), 1987, vol. 34, issue 2, 161-172

Abstract: In this article a new heuristic procedure is proposed. This procedure makes use of surrogate duality in solving multiconstraint knapsack problems. Computational effort involved in the procedure is bounded by a polynomial in the number of variables. Extensive computational testing indicates that the procedure generates good feasible solutions regardless of the problem structure. In 98% of the problems solved, the solution generated by the heuristic was within 1% of the optimal solution. This procedure was also tested against other heuristics and was found to compare favorably.

Date: 1987
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
https://doi.org/10.1002/1520-6750(198704)34:23.0.CO;2-A

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:34:y:1987:i:2:p:161-172

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 ().