Dynamic programming and strong bounds for the 0-1 knapsack problem

Two new algorithms recently proved to outperform all previous methods for t he exact solution of the 0-1 Knapsack Problem. This paper presents a combin ation of such approaches, where, in addition, valid inequalities are genera ted and surrogate relaxed, and a new initial core problem is adopted. The a lgorithm. is able to solve all classical test instances, with up to 10,000 variables, in less than 0.2 seconds on a HP9000-735/99 computer. The C lang uage implementation of the algorithm is available on the internet.