Premium
A heuristic solution procedure for the multiconstraint zero‐one knapsack problem
Author(s) -
Pirkul Hasan
Publication year - 1987
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/1520-6750(198704)34:2<161::aid-nav3220340203>3.0.co;2-a
Subject(s) - knapsack problem , zero (linguistics) , continuous knapsack problem , heuristic , mathematical optimization , change making problem , mathematics , polynomial time approximation scheme , cutting stock problem , computer science , optimization problem , philosophy , linguistics
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.