The binary knapsack problem: solutions with guaranteed quality

Diptesh Ghosh () and Boris Goldengorin
Additional contact information
Boris Goldengorin: Groningen University

No 01A64, Research Report from University of Groningen, Research Institute SOM (Systems, Organisations and Management)

Abstract: 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.

Date: 2001
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://irs.ub.rug.nl/ppn/237319497 (application/pdf)
Our link check indicates that this URL is bad, the error code is: 403 Forbidden (http://irs.ub.rug.nl/ppn/237319497 [302 Found]--> https://irs.ub.rug.nl/ppn/237319497 [302 Found]--> https://www.rug.nl/research/portal/publications/pub(0c856c7f-d268-49ba-aac4-4beba618d47e).html [301 Moved Permanently]--> https://research.rug.nl/en/publications/pub(0c856c7f-d268-49ba-aac4-4beba618d47e).html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gro:rugsom:01a64

Access Statistics for this paper

More papers in Research Report from University of Groningen, Research Institute SOM (Systems, Organisations and Management) Contact information at EDIRC.
Bibliographic data for series maintained by Hanneke Tamling ().