Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
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 a HP9000-735/99 computer. The C language implementation of the algorithm is available on the internet.
Volume (Year): 45 (1999)
Issue (Month): 3 (March)
|Contact details of provider:|| Postal: 7240 Parkway Drive, Suite 300, Hanover, MD 21076 USA|
Web page: http://www.informs.org/
More information through EDIRC
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Pisinger, David, 1995. "An expanding-core algorithm for the exact 0-1 knapsack problem," European Journal of Operational Research, Elsevier, vol. 87(1), pages 175-187, November.
- Freville, Arnaud & Plateau, Gerard, 1993. "An exact search for the solution of the surrogate dual of the 0-1 bidimensional knapsack problem," European Journal of Operational Research, Elsevier, vol. 68(3), pages 413-421, August.
- Silvano Martello & Paolo Toth, 1984. "A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem," Management Science, INFORMS, vol. 30(6), pages 765-771, June.
- Silvano Martello & Paolo Toth, 1988. "A New Algorithm for the 0-1 Knapsack Problem," Management Science, INFORMS, vol. 34(5), pages 633-644, May.