The binary knapsack problem: solutions with guaranteed quality

Diptesh Ghosh, Boris Goldengorin

Research output: Working paperAcademic

433 Downloads (Pure)


Binary knapsack problems are some of the most widely studied problems in combinatorial optimization. Several algorithms, both exact and approximate are known for this problem. In this paper, we embed heuristics within a branch and bound framework to produce an algorithm that generates solutions with guaranteed quality within very short times. We report computational experiments that show that for the more difficult strongly correlated problems, our algorithm can generate solutions within 0.01% of the optimal solution in less than 10% of the time required by exact algorithms.
Original languageEnglish
Number of pages20
Publication statusPublished - 2001

Cite this