Hard Knapsack Problems That Are Easy for Local Search

Chv'atal (1980) describes a class of zero-one knapsack problems provably difficult for branch and bound and dynamic programming algorithms. Chung et al. (1988) identifies a class of integer knapsack problems hard for branch and bound algorithms. We show that for both classes of problems local search provides optimal solutions quickly. Keywords : knapsack problem * local search * computational complexity Correspondence should be directed to the second author 1 Introduction Chv'atal (1980) describes a class of instances of zero-one knapsack problems due to Todd. ( We shall henceforth refer to these problems as the TODD class of problems. ) He shows that a wide class of algorithms --- including all based on branch and bound or dynamic programming --- find it difficult to solve problems in the TODD class. More precisely, the time required by these algorithms to solve instances of problems belonging to the TODD class grows as an exponential function of the problem parameters. Chung et a..