Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
AbstractTwo 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.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoArticle provided by INFORMS in its journal Management Science.
Volume (Year): 45 (1999)
Issue (Month): 3 (March)
Knapsack problem; dynamic programming; branch-and-bound; surrogate relaxation;
You can help add them by filling out this form.
CitEc Project, subscribe to its RSS feed for this item.
- Tang, Jiafu & Zhiqiao, Wu & Kwong, C.K. & Luo, Xinggang, 2013. "Integrated production strategy and reuse scenario: A CoFAQ model and case study of mail server system development," Omega, Elsevier, vol. 41(3), pages 536-552.
- Escudero, Laureano F. & Landete, Mercedes & Rodríguez-Chía, Antonio M., 2011. "Stochastic set packing problem," European Journal of Operational Research, Elsevier, vol. 211(2), pages 232-240, June.
- Klose, Andreas & Gortz, Simon, 2007. "A branch-and-price algorithm for the capacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 179(3), pages 1109-1125, June.
- Ghosh, Diptesh & Bandyopadhyay, Tathagata, . "Spotting Difficult Weakly Correlated Binary Knapsack Problems," IIMA Working Papers WP2006-01-04, Indian Institute of Management Ahmedabad, Research and Publication Department.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Mirko Janc).
If references are entirely missing, you can add them using this form.