A simulated annealing approach to the multiconstraint zero-one knapsack problem
作者： A. Drexl
DOI: 10.1007/BF02242185
关键词:
摘要: The multiconstraint 0–1 knapsack problem encounters when deciding how to use a with multiple resource constraints. is known be NP-hard, thus “good” algorithm for its optimal solution very unlikely exist. We show the concept of simulated annealing may used solving this approximately. 57 data sets from literature demonstrate, that converges rapidly towards optimum solution.
springer.com
acm.org
sci-hub.se 参考文章(23)
Eitan Zemel, Egon Balas, Solving Large Zero-One Knapsack Problems. ,(1977)
H. Telley, Th. M. Liebling, A. Mocellin, Reconstruction of polycrystalline structures: a new application of combinatorial optimization Computing. ,vol. 38, pp. 1- 11 ,(1987) , 10.1007/BF02253739
A. Freville, G. Plateau, Heuristics and reduction methods for multiple constraints 0–1 linear programming problems European Journal of Operational Research. ,vol. 24, pp. 206- 215 ,(1986) , 10.1016/0377-2217(86)90042-1
Michael Randolph Garey, Johnson: computers and intractability: a guide to the theory of np- completeness (freeman ,(1979)
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)
Egon Balas, Eitan Zemel, An Algorithm for Large Zero-One Knapsack Problems Operations Research. ,vol. 28, pp. 1130- 1154 ,(1980) , 10.1287/OPRE.28.5.1130
Y. Rossier, M. Troyon, Th. M. Liebling, Probabilistic exchange algorithms and Euclidean traveling salesman problems Or Spektrum. ,vol. 8, pp. 151- 164 ,(1986) , 10.1007/BF01784711
Ernesto Bonomi, Jean-Luc Lutton, The asymptotic behaviour of quadratic sum assignment problems: A statistical mechanics approach European Journal of Operational Research. ,vol. 26, pp. 295- 300 ,(1986) , 10.1016/0377-2217(86)90193-1
M.J. Magazine, Osman Oguz, A heuristic algorithm for the multidimensional zero-one knapsack problem European Journal of Operational Research. ,vol. 16, pp. 319- 326 ,(1984) , 10.1016/0377-2217(84)90286-8
Egon Balas, Clarence H. Martin, Pivot and Complement–A Heuristic for 0-1 Programming Management Science. ,vol. 26, pp. 86- 96 ,(1980) , 10.1287/MNSC.26.1.86