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.
Download Info
To download:
If you experience problems downloading a file, check if you have the
proper application to
view it first. Information about this may be contained
in the File-Format links below. In case of further problems read
the IDEAS help
page. Note that these files are not on the IDEAS
site. Please be patient as the files may be large.
Publisher Info
Paper provided by University of Groningen, Research Institute SOM (Systems, Organisations and Management) in its series Research Report with number
01A64.