Improved results on the 0–1 multidimensional knapsack problem
作者： Michel Vasquez , Yannick Vimont
DOI: 10.1016/J.EJOR.2004.01.024
关键词: Multidimensional analysis 、 Mathematical optimization 、 Tabu search 、 Constraint (information theory) 、 Continuous knapsack problem 、 Knapsack problem 、 Linear programming 、 Algorithm 、 Cutting-plane method 、 Mathematics 、 Heuristic (computer science)
摘要: Abstract Geometric Constraint and Cutting planes have been successfully used to solve the 0–1 multidimensional knapsack problem. Our algorithm combines Linear Programming with an efficient tabu search. It gives best results when compared other algorithms on benchmarks issued from OR-L ibrary . Embedding this in a variables fixing heuristic still improves our previous results. Furthermore difficult sub problems about 100 500 original ones could be generated. These small are always very hard solve.
elsevier.com
sci-hub.se 参考文章(21)
Oliver Wendt, Wolfgang König, Cooperative Simulated Annealing: How much cooperation is enough ? ,(1998)
Michel Vasquez, Resolution en variables 0-1 de problemes combinatoires de grande taille par la methode tabou Angers. ,(2000)
Bezalel Gavish, Hasan Pirkul, ALLOCATION OF DATA BASES AND PROCESSORS IN A DISTRIBUTED COMPUTING SYSTEM. North-Holland Publ Co. ,(1982)
Jin-Kao Hao, Michel Vasquez, A Hybrid Approach for the 01 Multidimensional Knapsack problem. international joint conference on artificial intelligence. pp. 328- 333 ,(2001)
María A. Osorio, Fred Glover, Peter Hammer, Cutting and Surrogate Constraint Analysis for Improved Multidimensional Knapsack Solutions Annals of Operations Research. ,vol. 117, pp. 71- 93 ,(2002) , 10.1023/A:1021513321301
A. Drexl, A simulated annealing approach to the multiconstraint zero-one knapsack problem Computing. ,vol. 40, pp. 1- 8 ,(1988) , 10.1007/BF02242185
Fred Glover, Gary A. Kochenberger, Critical Event Tabu Search for Multidimensional Knapsack Problems Springer, Boston, MA. pp. 407- 427 ,(1996) , 10.1007/978-1-4613-1361-8_25
P.C. Chu, J.E. Beasley, A Genetic Algorithm for the Multidimensional Knapsack Problem Journal of Heuristics. ,vol. 4, pp. 63- 86 ,(1998) , 10.1023/A:1009642405419
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
Saïd Hanafi, Arnaud Freville, An efficient tabu search approach for the 0–1 multidimensional knapsack problem European Journal of Operational Research. ,vol. 106, pp. 659- 675 ,(1998) , 10.1016/S0377-2217(97)00296-8