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

TLDR

The article proposes a new heuristic procedure for the multiconstraint zero‑one knapsack problem. The heuristic uses surrogate duality and its computational effort is bounded by a polynomial in the number of variables. Extensive testing shows the heuristic produces high‑quality solutions, achieving within 1% of optimal in 98% of cases and outperforming other heuristics.

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.