The binary knapsack problem: solutions with guaranteed quality

Diptesh Ghosh, Boris Goldengorin


437 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.
Originele taal-2English
Aantal pagina's20
StatusPublished - 2001

Citeer dit