Yet harder knapsack problems
Already 30 years ago. Chvatal has shown that some instances of the zero-one knapsack problem cannot be solved in polynomial time using a particular type of branch-and-bound algorithms based on relaxations of linear programs together with some rudimentary cutting-plane arguments as bounding rules. We extend this result by proving an exponential lower bound in a more general class of branch-and-bound and dynamic programming algorithms which are allowed to use memoization and arbitrarily powerful bound rules to detect and remove subproblems leading to no optimal solution. (C) 2011 Elsevier B.V. All rights reserved.
knapsack dynamic programming memoization branch and bound branching program perfect matching