New Greedy-Like Heuristics for the Multidimensional 0-1 Knapsack Problem
作者： Richard Loulou , Eleftherios Michaelides
关键词: Heuristic (computer science) 、 Cutting stock problem 、 Mathematics 、 Knapsack problem 、 Heuristics 、 Continuous knapsack problem 、 Change-making problem 、 Generalized assignment problem 、 Mathematical optimization 、 Management Science and Operations Research 、 Computer Science Applications
摘要: In this paper, we develop four heuristic methods to obtain approximate solutions the multidimensional 0-1 knapsack problem. The are tested on a number of problems various sizes. compared rigorous optimum as well method Toyoda. They statistically better than latter, with average relative errors order less 1%.
sci-hub.se 参考文章(10)
H. Martin Weingartner, Mathematical Programming and the Analysis of Capital Budgeting Problems ,(2018)
Yoshiaki Toyoda, A Simplified Algorithm for Obtaining Approximate Solutions to Zero-One Programming Problems Management Science. ,vol. 21, pp. 1417- 1427 ,(1975) , 10.1287/MNSC.21.12.1417
M. J. Magazine, G. L. Nemhauser, L. E. Trotter, When the Greedy Solution Solves a Class of Knapsack Problems Operations Research. ,vol. 23, pp. 207- 217 ,(1975) , 10.1287/OPRE.23.2.207
Clifford C. Petersen, Computational Experience with Variants of the Balas Algorithm Applied to the Selection of R&D Projects Management Science. ,vol. 13, pp. 736- 750 ,(1967) , 10.1287/MNSC.13.9.736
David N. Ness, H. Martin Weingartner, Method for the Solution of the Multi-Dimensional 0/1 Knapsack Problem ,(2011)
Harvey M. Salkin, Cornelis A. De Kluyver, The knapsack problem: A survey Naval Research Logistics Quarterly. ,vol. 22, pp. 127- 144 ,(1975) , 10.1002/NAV.3800220110
Giorgio Ingargiola, James F. Korsh, An Algorithm for the Solution of 0-1 Loading Problems Operations Research. ,vol. 23, pp. 1110- 1119 ,(1975) , 10.1287/OPRE.23.6.1110
James H. Lorie, Leonard J. Savage, Three Problems in Rationing Capital The Journal of Business. ,vol. 28, pp. 229- 239 ,(1955) , 10.1086/294081
Stelios H. Zanakis, Heuristic 0-1 Linear Programming: An Experimental Comparison of Three Methods Management Science. ,vol. 24, pp. 91- 104 ,(1977) , 10.1287/MNSC.24.1.91
Alexander A. Robichek, Martin H. Weingartner, Mathematical Programming and the Analysis of Capital Budgeting Problems. Journal of the American Statistical Association. ,vol. 60, pp. 675- ,(1965) , 10.2307/2282700