| Article ID: | iaor20002391 |
| Country: | United States |
| Volume: | 45 |
| Issue: | 3 |
| Start Page Number: | 414 |
| End Page Number: | 424 |
| Publication Date: | Mar 1999 |
| Journal: | Management Science |
| Authors: | Martello Silvano, Toth Paolo, Pisinger David |
| Keywords: | programming: branch and bound |
Two new algorithms recently proved to outperform all previous methods for the exact solution of the 0–1 Knapsack Problem. This paper presents a combination of such approaches, where, in addition, valid inequalities are generated and surrogate relaxed, and a new initial core problem is adopted. The algorithm is able to solve all classical test instances, with up to 10,000 variables, in less than 0.2 seconds on an HP9000-735/99 computer. The C language implementation of the algorithm is available on the internet.