Core Problems in Knapsack Algorithms

Since Balas and Zemel in the 1980s introduced the so-called core problem as an efficient tool for solving the Knapsack Problem, all the most successful algorithms have applied this concept. Balas and Zemel proved that if the weights in the core are uniformly distributed then there is a high probability for finding an optimal solution in the core. Items outside the core may be fathomed because of reduction rules.This paper demonstrates that generally it is not reasonable to assume a uniform distribution of the weights in the core, and it is experimentally shown that the heuristic proposed by Balas and Zemel does not find as good solutions as expected. Also, other algorithms that solve some kind of core problem may be stuck by difficult cores. This behavior has apparently not been noticed before because of unsufficient testing.Capacities leading to difficult problems are identified for several categories of instance types, and it is demonstrated that the hitherto applied test instances are easier than the average. As a consequence we propose a series of new randomly generated test instances and show how recent algorithms behave when applied to these problems.