| Article ID: | iaor1988728 |
| Country: | United States |
| Volume: | 35 |
| Issue: | 1 |
| Start Page Number: | 85 |
| End Page Number: | 98 |
| Publication Date: | Feb 1988 |
| Journal: | Naval Research Logistics |
| Authors: | Hung Ming S., Chung Chia-Shin, Rom Walter O. |
| Keywords: | knapsack problem |
In this article the authors develop a class of general knapsack problems which are hard for branch and bound algorithms. The number of alternate optimal solutions for these problems grows exponentially with problem parameters. In addition the LP bound is shown to be ineffective. Computational tests indicate that these problems are truly difficult for evey very small problems. Implications for the testing of algorithms using randomly generated problems is discussed.