Obtaining Near OptimalSolutions for the Binary Knapsack Problem
Research & Publications
Obtaining Near OptimalSolutions for the Binary Knapsack Problem
03/02/2002
Obtaining Near OptimalSolutions for the Binary Knapsack Problem
Diptesh Ghosh and Boris Goldengorin
Working Papers
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.