Premium
A hard knapsack problem
Author(s) -
Chung ChiaShin,
Hung Ming S.,
Rom Walter O.
Publication year - 1988
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(198802)35:1<85::aid-nav3220350108>3.0.co;2-d
Subject(s) - knapsack problem , continuous knapsack problem , mathematical optimization , cutting stock problem , mathematics , branch and bound , class (philosophy) , change making problem , upper and lower bounds , computer science , optimization problem , artificial intelligence , mathematical analysis
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.