A hard knapsack problem |
| |
| Authors: | Chia-Shin Chung Ming S. Hung Walter O. Rom |
| |
| Affiliation: | 1. Department of Quantitative Business Analysis, Cleveland State University, Cleveland, Ohio 44115;2. Graduate School of Management, Kent State University, Kent, Ohio 44242 |
| |
| Abstract: | In this article we 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 even very small problems. Implications for the testing of algorithms using randomly generated problems is discussed. |
| |
| Keywords: | |
|
|
