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

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.