Obtaining near-optimal solutions for the binary knapsack problem

Abstract

In this paper we consider the well-known binary knapsack problem. We propose a method of embedding heuristicsi in a branch and bound framework to optain solutions with profits within a pre-specified quality parameter within very short times. Our computational experiements on the more deficult problems show that algorithm can genrate solutions with profits within 0.01% of that of an optimal solution in less than 10% of the time required by exact algorithms based on similar priciples.