The 0/1 Multidimensional Knapsack Problem (0/1 MKP) is an interesting
NP-hard combinatorial optimization problem that can model a number of
challenging applications in logistics, finance, telecommunications and other
fields. In the 0/1 MKP, a set of items is given, each with a size and value,
which has to be placed into a knapsack that has a certain number of dimensions
having each a limited capacity. The goal is to find a subset of items
leading to the maximum total profit while respecting the capacity constraints.
Even though the 0/1 MKP is well studied in the literature, we can just find a
little number of recent review papers on this problem. Furthermore, the existing
reviews focus particularly on some specific issues. This paper aims to
give a general and comprehensive survey of the considered problem so that it
can be useful for both researchers and practitioners. Indeed, we first describe
the 0/1 MKP and its relevant variants. Then, we present the detailed models
of some important real-world applications of this problem. Moreover, an
important collection of recently published heuristics and metaheuristics is
categorized and briefly reviewed. These approaches are then quantitatively
compared through some indicative statistics. Finally, some synthetic remarks
and research directions are highlighted in the conclusion.
References
[1]
Martello, S. and Toth, P. (1990) Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons Ltd., Chichester.
[2]
Skiena, S. (1999) Who Is Interested in Algorithms and Why? Lessons from the Stony Brook Algorithms Repository. ACM SIGACT News, 30, 65-74. https://doi.org/10.1145/333623.333627
[3]
Eilon, S. and Christofides, N. (1971) The Loading Problem. Management Science, 17, 259-268. https://doi.org/10.1287/mnsc.17.5.259
[4]
Hifi, M. (2009) Approximate Algorithms for the Container Loading Problem. Operations Research, 9, 747-774.
[5]
Gilmore, P.C. and Gomory, R.E. (1966) The Theory and Computation of Knapsack Functions. Operations Research, 14, 1045-1074. https://doi.org/10.1287/opre.14.6.1045
[6]
Labbé, M., Laporte, G. and Martello, S. (2003) Upper Bounds and Algorithms for the Maximum Cardinality Bin Packing Problem. European Journal of Operational Research, 149, 490-498. https://doi.org/10.1016/S0377-2217(02)00466-6
[7]
Petersen, C.C. (1967) Computational Experience with Variants of the Balas Algorithm Applied to the Selection of R&D Projects. Management Science, 3, 736-750. https://doi.org/10.1287/mnsc.13.9.736
[8]
Weingartner, H.M. (1966) Capital Budgeting of Interrelated Projects: Survey and Synthesis. Management Science, 12, 485-516. https://doi.org/10.1287/mnsc.12.7.485
[9]
Lorie, J.H. and Savage, L.J. (1955) Three Problems in Rationing Capital. The Journal of Business, 28, 229-239. https://doi.org/10.1086/294081
[10]
Markowitz, H.M. and Manne, A.S. (1957) On the Solution of Discrete Programming Problems. Econometrica Journal of the Econometric Society, 25, 84-110. https://doi.org/10.2307/1907744
[11]
Kellerer, H., Pferschy, U. and Pisinger, D. (2004) Knapsack Problems. Springer, Berlin. https://doi.org/10.1007/978-3-540-24777-7
[12]
Freville, A. (2004) The Multidimensional 0-1 Knapsack Problem: An Overview. European Journal of Operational Research, 155, 1-21. https://doi.org/10.1016/S0377-2217(03)00274-1
[13]
Gavish, B. and Pirkul, H. (1965) Efficient Algorithms for Solving Multiconstraint Zero-One Knapsack Problems to Optimality. Mathematical Programming, 31, 78-105. https://doi.org/10.1007/BF02591863
[14]
Chu, P.C. and Beasley, J.E. (1998) A Genetic Algorithm for the Multidimensional Knapsack Problem. Journal of heuristics, 4, 63-86. https://doi.org/10.1023/A:1009642405419
[15]
Lai, G., Yuan, D. and Yang, S. (2014) A New Hybrid Combinatorial Genetic Algorithm for Multidimensional Knapsack Problems. Journal of Supercomputing, 70, 930-945. https://doi.org/10.1007/s11227-014-1268-9
[16]
Varnamkhasti, M.J. (2012) Overview of the Algorithms for Solving the Multidimensional Knapsack Problems. Advanced Studies in Biology, 4, 37-47.
[17]
Puchinger, J., Raidl, G.R. and Pferschy, U. (2010) The Multidimensional Knapsack Problem: Structure and Algorithms. INFORMS Journal on Computing, 22, 250-265. https://doi.org/10.1287/ijoc.1090.0344
[18]
Lust, T. and Teghem, J. (2012) The Multiobjective Multidimensional Knapsack Problem: A Survey and a New Approach. International Transactions in Operational Research, 19, 495-520. https://doi.org/10.1111/j.1475-3995.2011.00840.x
[19]
Lienland, B. and Zeng, L.A. (2015) Review and Comparison of Genetic Algorithms for the 0-1 Multidimensional Knapsack Problem. International Journal of Operations Research and Information Systems, 6, 21-31. https://doi.org/10.4018/ijoris.2015040102
[20]
Alonso, C.L., Caro, F. and Montaña, J.L. (2006) A Flipping Local Search Genetic Algorithm for the Multidimensional 0-1 Knapsack Problem. Lecture Notes in Computer Science, 4177, 21-30. https://doi.org/10.1007/11881216_3
[21]
Dyer, M.E., Riha, W.O. and Walker, J. (1995) A Hybrid Dynamic Programming/Branch-and-Bound Algorithm for the Multiple-Choice Knapsack Problem. Journal of Computational and Applied Mathematics, 58, 43-54. https://doi.org/10.1016/0377-0427(93)E0264-M
[22]
Gallardo, J. E., Cotta, C. and Fernández, A.J. (2005) Solving the Multidimensional Knapsack Problem Using an Evolutionary Algorithm Hybridized with Branch and Bound. Lecture Notes in Computer Science, 3562, 21-30. https://doi.org/10.1007/11499305_3
[23]
Jourdan, L., Basseur, M. and Talbi, E.G. (2009) Hybridizing Exact Methods and Metaheuristics: A Taxonomy. European Journal of Operational Research, 199, 620-629. https://doi.org/10.1016/j.ejor.2007.07.035
[24]
Schulze, B. (2017) New Perspectives on Multi-Objective Knapsack Problems. Ph.D. Thesis, University of Wuppertal, Germany. http://elpub.bib.uni-wuppertal.de/servlets/DerivateServlet/Derivate-6701/dc1706.pdf
[25]
Kunikazu, Y. and Prékopa, A. (2012) Convexity and Solutions of Stochastic Multidimensional Knapsack Problems with Probabilistic Constraints. Research report. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.304.5298
[26]
Pfeiffer, J. and Rothlauf, F. (2007) Analysis of Greedy Heuristics and Weight-Coded EAs for Multidimensional Knapsack Problems and Multi-Unit Combinatorial Auctions. Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation (GECCO-2007), ACM, London, 7-11 July 2007, 1529-1529.
[27]
Holte, R.C. (2001) Combinatorial Auctions, Knapsack Problems, and Hill-Climbing Search. Proceedings of the 14th Conference of the Canadian Society for Computational Studies of Intelligence (AI 2001), Ottawa, 7-9 June 2001, 57-66.
[28]
Kelly, T. (2004) Generalized Knapsack Solvers for Multi-Unit Combinatorial Auctions: Analysis and Application to Computational Resource Allocation. Proceedings of the International Workshop on Agent Mediated-Electronic Commerce VI: Theories for and Engineering of Distributed Mechanisms and Systems (AMEC 2004), New York, NY, 19 July 2004, 73-86.
[29]
Chen, F., La Porta, T. and Srivastava, M.B. (2012) Resource Allocation with Stochastic Demands. Proceedings of the IEEE 8th International Conference on Distributed Computing in Sensor Systems (DCOSS 2012), Hangzhou, 16-18 May 2012, 257-264.
[30]
Luedtke, J. and Ahmed, S. (2008) A Sample Approximation Approach for Optimization with Probabilistic Constraints. SIAM Journal on Optimization, 19, 674-699. https://doi.org/10.1137/070702928
[31]
Mitola, J. and Maguire, G. (1999) Cognitive Radio: Making Software Radios More Personal. IEEE Personal Communications, 6, 13-18. https://doi.org/10.1109/98.788210
[32]
Song, Y., Zhang, C. and Fang, Y. (2008) Multiple Multidimensional Knapsack Problem and Its Applications in Cognitive Radio Networks. Proceedings of the IEEE Military Communications Conference (MILCOM 2008), San Diego, 16-19 November 2008, 1-7.
[33]
Ykman-Couvreur, C., Nollet, V., Catthoor, F. and Corporaal, H. (2011) Fast Multidimension Multichoice Knapsack Heuristic for MP-SoC Runtime Management. ACM Transactions on Embedded Computing Systems (TECS), 10, Article No. 35. https://doi.org/10.1145/1952522.1952528
[34]
Mejia-Alvarez, E., Levner, P. and Mosse, D. (2002) Power-Optimized Scheduling Server for Real-Time Tasks. Proceedings of the IEEE 8th Real-Time and Embedded Technology and Applications Symposium (RTAS 2002), San Jose, 25-27 September 2002, 239-250.
[35]
Khalili-Damghani, K. and Taghavifard, M. (2011) Solving a Bi-Objective Project Capital Budgeting Problem Using a Fuzzy Multi-Dimensional Knapsack. Journal of Industrial Engineering International, 7, 67-73.
[36]
Taillandier, F., Fernandez, C. and Ndiaye, A. (2017) Real Estate Property Maintenance Optimization Based on Multiobjective Multidimensional Knapsack Problem. Computer-Aided Civil and Infrastructure Engineering, 32, 227-251. https://doi.org/10.1111/mice.12246
[37]
Toyoda, Y. (1975) A Simplified Algorithm for Obtaining Approximate Solutions to Zero-One Programming Problems. Management Science, 21, 1417-1427. https://doi.org/10.1287/mnsc.21.12.1417
[38]
Raidl, G.R. (1999) Weight-Codings in a Genetic Algorithm for the Multiconstraint Knapsack Problem. Proceedings of the IEEE Congress on Evolutionary Computation (CEC 1999), Washington DC, 6-9 July 1999, 596-603.
[39]
Senju, S. and Toyoda, Y. (1968) An Approach to Linear Programming with 0-1 Variables. Management Science, 15, 196-207. https://doi.org/10.1287/mnsc.15.4.B196
[40]
Volgenant, A. and Zwiers, I.Y. (2007) Partial Enumeration in Heuristics for Some Combinatorial Optimization Problems. Journal of Operational Research Society, 58, 73-79. https://doi.org/10.1057/palgrave.jors.2602102
[41]
Akin, M.H. (2009) New Heuristics for the 0-1 Multi-Dimensional Knapsack Problems. Ph.D. Thesis, University of Central Florida, USA. http://purl.fcla.edu/fcla/etd/CFE0002633
[42]
Akcay, Y., Li, H. and Xu, S.H. (2007) Greedy Algorithm for the General Multidimensional Knapsack Problem. Annals of Operations Research, 150, 17-29. https://doi.org/10.1007/s10479-006-0150-4
[43]
Drake, J.H., Hyde, M., Ibrahim, K. and Ozcan, E. (2014) A Genetic Programming Hyper-Heuristic for the Multidimensional Knapsack Problem. Kybernetes, 43, 1500-1511. https://doi.org/10.1108/K-09-2013-0201
[44]
Libao, D., Sha, W., Chengyu, J. and Cong, H. (2016) A Hybrid Mutation Scheme-Based Discrete Differential Evolution Algorithm for Multidimensional Knapsack Problem. Proceedings of the IEEE 6th International Conference on Instrumentation & Measurement, Computer, Communication and Control (IMCCC 2016), Harbin, 21-23 July 2016, 1009-1014.
[45]
Crawford, B., Soto, R., Astorga, G., García, J., Castro, C. and Paredes, F. (2017) Putting Continuous Metaheuristics to Work in Binary Search Spaces. Complexity, 2017, 19. https://doi.org/10.1155/2017/8404231
[46]
Hanafi, S. and Wilbaut, C. (2009) Improved Convergent Heuristics for the 0-1 Multidimensional Knapsack Problem. Annals of Operations Research, 183, 125-142. https://doi.org/10.1007/s10479-009-0546-z
[47]
Soyster, A.L., Lev, B. and Slivka, W. (1978) Zero-One Programming with Many Variables and Few Constraints. European Journal of Operational Research, 2, 195-201. https://doi.org/10.1016/0377-2217(78)90093-0
[48]
Crévits, I., Hanafi, S., Mansi, R. and Wilbaut, C. (2012) Iterative Semi-Continuous Relaxation Heuristics for the Multiple-Choice Multidimensional Knapsack Problem. Computers & Operations Research, 39, 32-41. https://doi.org/10.1016/j.cor.2010.12.016
[49]
Yoon, Y. and Kim, Y.H. (2013) A Memetic Lagrangian Heuristic for the 0-1 Multidimensional Knapsack Problem. Discrete Dynamics in Nature and Society, 2013, 10. https://doi.org/10.1155/2013/474852
[50]
Atılgan, C. and Nuriyev, U. (2012) Hybrid Heuristic Algorithm for the Multidimensional Knapsack Problem. Proceedings of the IEEE 4th International Conference on Problems of Cybernetics and Informatics, Baku, 12-14 September 2012, 1-4.
[51]
Beasley, J.E. (1990) OR-Library: Distributing Test Problems by Electronic Mail. Journal of the Operational Research Society, 41, 1069-1072. https://doi.org/10.1057/jors.1990.166
[52]
Yoon, Y. and Kim, Y.H. (2012) A Theoretical and Empirical Investigation on the Lagrangian Capacities of the 0-1 Multidimensional Knapsack Problem. European Journal of Operational Research, 218, 366-376. https://doi.org/10.1016/j.ejor.2011.11.011
[53]
Hill, R.R., Cho, Y.K. and Moore, J.T. (2012) Problem Reduction Heuristic for the 0-1 Multidimensional Knapsack Problem. Computers & Operations Research, 39, 19-26. https://doi.org/10.1016/j.cor.2010.06.009
[54]
Montaña, J.L., Alonso, C.L., Cagnoni, S. and Callau, M. (2008) Computing Surrogate Constraints for Multidimensional Knapsack Problems Using Evolution Strategies. Proceedings of the Workshops on Applications of Evolutionary Computation, Naples, 26-28 March 2008, 555-564.
[55]
Boyer, V., Elkihel, M. and El Baz, D. (2009) Heuristics for the 0-1 Multidimensional Knapsack Problem. European Journal of Operational Research, 199, 658-664. https://doi.org/10.1016/j.ejor.2007.06.068
[56]
Bas, E. (2012) Surrogate Relaxation of a Fuzzy Multidimensional 0-1 Knapsack Model by Surrogate Constraint Normalization Rules and a Methodology for Multi-Attribute Project Portfolio Selection. Engineering Applications of Artificial Intelligence, 25, 958-970. https://doi.org/10.1016/j.engappai.2011.09.015
[57]
Htiouech, S., Bouamama, S. and Attia, R. (2013) Using Surrogate Information to Solve the Multidimensional Multi-Choice Knapsack Problem. Proceedings of the IEEE Congress on Evolutionary Computation, Cancun, 20-23 June 2013, 2102-2107.
Crama, Y. and Mazzola, J.B. (1994) On the Strength of Relaxations of Multidimensional Knapsack Problems. INFOR: Information Systems and Operational Research, 32, 219-225. https://doi.org/10.1080/03155986.1994.11732252
[60]
Hiremath, C.S. and Hill, R.R. (2013) First-Level Tabu Search Approach for Solving the Multiple-Choice Multidimensional Knapsack Problem. International Journal of Metaheuristics, 2, 174-199. https://doi.org/10.1504/IJMHEUR.2013.054150
[61]
Khan, S., Li, K.F., Manning, E.G. and Akbar, M. (2002) Solving the Knapsack Problem for Adaptive Multimedia Systems. Studia Informatica, 2, 157-178.
[62]
Li, V.C, Liang, Y.C. and Chang, H.F. (2012) Solving the Multidimensional Knapsack Problems with Generalized Upper Bound Constraints by the Adaptive Memory Projection Method. Computers & Operations Research, 39, 2111-2121. https://doi.org/10.1016/j.cor.2011.10.016
[63]
Li, V.C., Curry, G.L. and Boyd, E.A. (2004) Towards the Real Time Solution of Strike Force Asset Allocation Problems. Computers & Operations Research, 31, 273-291. https://doi.org/10.1016/S0305-0548(02)00192-2
[64]
Li, V.C. (2008) A Perturbation-Guided Oscillation Strategy for the Multidimensional Knapsack Problem with Generalized Upper Bound Constraints. Proceedings of the 7th International Symposium on Operations Research and Its Applications, Lijiang, 31 October-3 November 2008, 369-376.
[65]
Khemakhem, M., Haddar, B., Chebil, K. and Hanafi, S. (2012) A Filter-and-Fan Metaheuristic for the 0-1 Multidimensional Knapsack Problem. International Journal of Applied Metaheuristic Computing, 3, 43-63. https://doi.org/10.4018/jamc.2012100103
[66]
Alidaee, B., Ramalingam, V.P., Wang, H. and Kethley, B. (2017) Computational Experiment of Critical Event Tabu Search for the General Integer Multidimensional Knapsack Problem. Annals of Operations Research, 269, 17.
[67]
Hanafi, S., Lazić, J., Mladenović, N. and Wilbaut, C. (2009) Variable Neighbourhood Decomposition Search with Bounding for Multidimensional Knapsack Problem. IFAC Proceedings Volumes, 42, 2018-2022. https://doi.org/10.3182/20090603-3-RU-2001.0502
[68]
Turajlić, N. and Dragović, I. (2012) A Hybrid Metaheuristic Based on Variable Neighborhood Search and Tabu Search for the Web Service Selection Problem. Electronic Notes in Discrete Mathematics, 39, 145-152. https://doi.org/10.1016/j.endm.2012.10.020
[69]
Puchinger, J., Raidl, G.R. and Pferschy, U. (2006) The Core Concept for the Multidimensional Knapsack Problem. Proceedings of the 6th European Conference on Evolutionary Computation in Combinatorial Optimization, Budapest, 10-12 April 2006, 195-208. https://doi.org/10.1007/11730095_17
[70]
Hansen, P. and Mladenovic, N. (2005) Variable Neighborhood Search. In: Burke E.K. and Kendall, G., Eds., Search Methodologies, Springer, Berlin, 211-238. https://doi.org/10.1007/0-387-28356-0_8
[71]
Puchinger, J. and Raidl, G.R. (2008) Bringing Order into the Neighborhoods: Relaxation Guided Variable Neighborhood Search. Journal of Heuristics, 14, 457-472. https://doi.org/10.1007/s10732-007-9048-9
[72]
Gupta, S. and Arora, S. (2015) Boosting Simulated Annealing with Fitness Landscape Parameters for Better Optimality. International Journal of Computing, 14, 107-112.
[73]
Leung, S.C., Zhang, D., Zhou, C. and Wu, T. (2012) A Hybrid Simulated Annealing Metaheuristic Algorithm for the Two-Dimensional Knapsack Packing Problem. Computers & Operations Research, 39, 64-73. https://doi.org/10.1016/j.cor.2010.10.022
[74]
Fang, Z., Gu, X. and Chen, J. (2017) Improved Heuristic Flower Pollination Algorithm for Solving Multi-Dimensional Knapsack Problems. Proceedings of the IEEE 10th International Conference on Intelligent Computation Technology and Automation, Changsha, 9-10 October 2017, 33-38.
[75]
Yang, X.S. (2012) Flower Pollination Algorithm for Global Optimization. Proceedings of the 11th International Conference on Unconventional Computing and Natural Computation, Orléans, 3-7 September 2012, 240-249. https://doi.org/10.1007/978-3-642-32894-7_27
[76]
Malossini, A., Blanzieri, E. and Calarco, T. (2008) Quantum Genetic Optimization. IEEE Transactions on Evolutionary Computation, 12, 231-241. https://doi.org/10.1109/TEVC.2007.905006
[77]
Varnamkhasti, M.J. and Lee, L.S. (2012) A Genetic Algorithm Based on Sexual Selection for the Multidimensional 0/1 Knapsack Problems. International Journal of Modern Physics: Conference Series, 9, 422-431.
[78]
Varnamkhasti. M.J. and Lee, L.S. (2012) A Fuzzy Genetic Algorithm Based on Binary Encoding for Solving Multidimensional Knapsack Problems. Journal of Applied Mathematics, 2012, 23.
[79]
Raidl, G.R. (1998) An Improved Genetic Algorithm for the Multiconstrained 0-1 Knapsack Problem. Proceedings of the IEEE World Congress on Computational Intelligence, Anchorage, 4-9 May 1998, 207-211.
[80]
Yang, H., Wang, M. and Yang, C. (2013) A Hybrid of Rough Sets and Genetic Algorithms for Solving the 0-1 Multidimensional Knapsack Problem. International Journal of Innovative Computing, Information and Control, 9, 3537-3548.
[81]
Pawlak, Z. (1982) Rough Set. International Journal of Information and Computer Science, 11, 341-356. https://doi.org/10.1007/BF01001956
[82]
Liu, X., Xiang, F. and Mao, J. (2014) An Improved Method for Solving the Large-Scale Multidimensional 0-1 Knapsack Problem. Proceedings of the IEEEInternational Conference on Electronics and Communication Systems, Coimbatore, 13-14 February 2014,1-6.
[83]
Tisna, F.D., Abusini, S. and Andari, A. (2013) Hybrid Greedy-Particle Swarm Optimization-Genetic Algorithm and Its Convergence to Solve Multidimensional Knapsack Problem 0-1. Journal of Theoretical & Applied Information Technology, 58, 522-529.
[84]
Rezoug, A., Boughaci, D. and Badr-El-Den, M. (2015) Memetic Algorithm for Solving the 0-1 Multidimensional Knapsack Problem. Proceedings of the Portuguese Conference on Artificial Intelligence, Coimbra, 8-11 September 2015, 298-304.
[85]
Martins, J.P., Fonseca, C.M. and Delbem, A.C. (2014) On the Performance of Linkage-Tree Genetic Algorithms for the Multidimensional Knapsack Problem. Neurocomputing, 146, 17-29. https://doi.org/10.1016/j.neucom.2014.04.069
[86]
Yang, H.H., Wang, M.T., Chen, Y.J. and Kao, C.J. (2010) Crossover Based on Rough Sets: A Case of Multidimensional Knapsack Problem. Proceedings of the IEEE International Conference on Industrial Engineering and Engineering Management, Macao, 7-10 December 2010, 2411-2415.
[87]
Rezoug, A., Bader-El-Den, M. and Boughaci, D. (2017) Guided Genetic Algorithm for the Multidimensional Knapsack Problem. Memetic Computing, 10, 14.
[88]
Rezoug, A., Bader-El-Den, M. and Boughaci, D. (2017) Knowledge-Based Genetic Algorithm for the 0-1 Multidimensional Knapsack Problem. Proceedings of the IEEE Congress on Evolutionary Computation, San Sebastian, 5-8 June 2017, 2030-2037.
[89]
Aghezzaf, B. and Naimi, M. (2009) The Two-Stage Recombination Operator and Its Application to the Multiobjective 0/1 Knapsack Problem: A Comparative Study. Computers & Operations Research, 36, 3247-3262. https://doi.org/10.1016/j.cor.2009.02.027
[90]
Deane, J. and Agarwal, A. (2013) Neural, Genetic and Neurogenetic Approaches for Solving the 0-1 Multidimensional Knapsack Problem. International Journal of Management & Information Systems, 17, 43-54.
[91]
da Silva, D.J.A., Teixeira, O.N. and de Oliveira, R.C.L. (2012) Performance Study of Cultural Algorithms Based on Genetic Algorithm with Single and Multi-Population for the MKP. In: Gao, S.C., Ed., Bio-Inspired Computational Algorithms and Their Applitions, IntechOpen, 385-404.
[92]
Aguirre, H.E., Tanaka, K., Sugimara, T. and Oshita, S. (2000) Improved Distributed Genetic Algorithm with Cooperative-Competitive Genetic Operators. Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, Nashville, 8-11 October 2000, 3816-3822. https://doi.org/10.1109/ICSMC.2000.886605
[93]
Gupta, I.K., Choubey, A. and Choubey, S. (2017) Clustered Genetic Algorithm to Solve Multidimensional Knapsack Problem. Proceedings of the 8th International Conference on Computing, Communication and Networking Technologies, Delhi , 3-5 July 2017, 1-6.
[94]
Leguizamon, G. and Michalewicz, Z. (1999) A New Version of Ant System for Subset Problems. Proceedings of the IEEE Congress on Evolutionary Computation, Washington DC, 6-9 July 1999, 1459-1464.
[95]
Iqbal, S., Bari, M.F. and Rahman, M.S. (2010) Solving the Multi-Dimensional Multi-Choice Knapsack Problem with the Help of Ants. Proceedings of the International Conference on Swarm Intelligence, Beijing, 12-15 June 2010, 312-323. https://doi.org/10.1007/978-3-642-15461-4_27
[96]
Ren, Z., Feng, Z. and Zhang, A. (2012) Fusing Ant Colony Optimization with Lagrangian Relaxation for the Multiple-Choice Multidimensional Knapsack Problem. Information Sciences, 182, 15-29. https://doi.org/10.1016/j.ins.2011.07.033
[97]
Nakbi, W., Alaya, I. and Zouari, W. (2015) A Hybrid Lagrangian Search Ant Colony Optimization Algorithm for the Multidimensional Knapsack Problem. Procedia Computer Science, 60, 1109-1119. https://doi.org/10.1016/j.procs.2015.08.158
[98]
Ke, L., Feng, Z., Ren, Z. and Wei, X. (2010) An Ant Colony Optimization Approach for the Multidimensional Knapsack Problem. Journal of Heuristics, 16, 65-83. https://doi.org/10.1007/s10732-008-9087-x
[99]
Kong, M., Tian, P. and Kao, Y. (2008) A New Ant Colony Optimization Algorithm for the Multidimensional Knapsack Problem. Computers & Operations Research, 35, 2672-2683. https://doi.org/10.1016/j.cor.2006.12.029
[100]
Al-Shihabi, S. and ólafsson, S. (2010) A Hybrid of Nested Partition, Binary Ant System and Linear Programming for the Multidimensional Knapsack Problem. Computers & Operations Research, 37, 247-255. https://doi.org/10.1016/j.cor.2009.04.015
[101]
Liu, R.T. and Lv, X.J. (2013) Map Reduce-Based Ant Colony Optimization Algorithm for Multi-Dimensional Knapsack Problem. Applied Mechanics and Materials, 380-384, 4.
[102]
Fingler, H., Cáceres, E.N., Mongelli, H. and Song, S.W. (2014) A CUDA Based Solution to the Multidimensional Knapsack Problem Using the Ant Colony Optimization. Procedia Computer Science, 29, 84-94. https://doi.org/10.1016/j.procs.2014.05.008
[103]
Solnon, C. and Bridge, D. (2006) An Ant Colony Optimization Meta-Heuristic for Subset Selection Problems. In: Nedjah, N. and Mourelle, L., Eds., System Engineering Using Particle Swarm Optimization, Nova Science, Hauppauge, 7-29.
[104]
Mansour, I.B. and Alaya, I. (2015) Indicator Based Ant Colony Optimization for Multi-Objective Knapsack Problem. Procedia Computer Science, 60, 448-457. https://doi.org/10.1016/j.procs.2015.08.165
[105]
Iqbal, S., Bari, M.F. and Rahman, M.S. (2010) A Novel ACO Technique for Fast and near Optimal Solutions for the Multi-Dimensional Multi-Choice Knapsack Problem. Proceedings of the 13th IEEE International Conference on Computer and Information Technology, Dhaka, 23-25 December 2010, 33-38.
[106]
Chen, W.N., Zhang, J., Chung, H.S., Zhong, W.L., Wu, W.G. and Shi, Y.H. (2010) A Novel Set-Based Particle Swarm Optimization Method for Discrete Optimization Problems. IEEE Transactions on Evolutionary Computation, 14, 278-300. https://doi.org/10.1109/TEVC.2009.2030331
[107]
Langeveld, J. and Engelbrecht, A.P. (2012) Set-Based Particle Swarm Optimization Applied to the Multidimensional Knapsack Problem. Swarm Intelligence, 6, 297-342. https://doi.org/10.1007/s11721-012-0073-4
[108]
Gherboudj, A., Labed, S. and Chikhi, S. (2012) A New Hybrid Binary Particle Swarm Optimization Algorithm for Multidimensional Knapsack Problem. In: Wyld, D., Zizka, J. and Nagamalai, D., Eds., Advances in Computer Science, Engineering & Applications, Springer, Berlin, 489-498. https://doi.org/10.1007/978-3-642-30157-5_49
[109]
Langeveld, J. and Engelbrecht, A.P. (2011) A Generic Set-Based Particle Swarm Optimization Algorithm. Proceedings of the International Conference on Swarm Intelligence, Chongqing, 12-15 June 2011, 1-10.
[110]
Franken, N. (2009) Visual Exploration of Algorithm Parameter Space. Proceedings of the IEEE Congress on Evolutionary Computation, Trondheim, 18-21 May 2009, 389-398.
[111]
Chih, M., Lin, C.J., Chern, M.S. and Ou, T.Y. (2014) Particle Swarm Optimization with Time-Varying Acceleration Coefficients for the Multidimensional Knapsack Problem. Applied Mathematical Modelling, 38, 1338-1350. https://doi.org/10.1016/j.apm.2013.08.009
[112]
Lin, C.J., Chern, M.S. and Chih, M. (2016) A Binary Particle Swarm Optimization Based on the Surrogate Information with Proportional Acceleration Coefficients for the 0-1 Multidimensional Knapsack Problem. Journal of Industrial and Production Engineering, 33, 77-102. https://doi.org/10.1080/21681015.2015.1111263
[113]
Haddar, B., Khemakhem, M., Hanafi, S. and Wilbaut, C. (2016) A hybrid Quantum Particle Swarm Optimization for the Multidimensional Knapsack Problem. Engineering Applications of Artificial Intelligence, 55, 1-13. https://doi.org/10.1016/j.engappai.2016.05.006
[114]
Chih, M. (2015) Self-Adaptive Check and Repair Operator-Based Particle Swarm Optimization for the Multidimensional Knapsack Problem. Applied Soft Computing, 26, 378-389. https://doi.org/10.1016/j.asoc.2014.10.030
[115]
Chih, M. (2017) A Three-Ratio SACRO-Based Particle Swarm Optimization with Local Search Scheme for the Multidimensional Knapsack Problem. Proceedings of the 18th IEEE/ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing, Kanazawa, 26-28 June 2017, 17-22.
[116]
Chih, M. (2017) Three Pseudo-Utility Ratio-Inspired Particle Swarm Optimization with Local Search for Multidimensional Knapsack Problem. Swarm and Evolutionary Computation, 39, 18.
[117]
Zan, D. and Jaros, J. (2014) Solving the Multidimensional Knapsack Problem Using a CUDA Accelerated PSO. Proceedings of the IEEE Congress on Evolutionary Computation, Beijing, 6-11 July 2014, 2933-2939.
[118]
Weingartner, H.M. and Ness, D.N. (1967) Methods for the Solution of the Multi-Dimensional 0/1 Knapsack Problem. Operations Research, 15, 83-103. https://doi.org/10.1287/opre.15.1.83
[119]
Bonyadi, M.R. and Michalewicz, Z. (2012) A Fast Particle Swarm Optimization Algorithm for the Multidimensional Knapsack Problem. Proceedings of the IEEE Congress on Evolutionary Computation, Brisbane, 10-15 June 2012, 1-8.
[120]
Ktari, R. and Chabchoub, H. (2013) Essential Particle Swarm Optimization Queen with Tabu Search for MKP Resolution. Computing, 95, 897-921. https://doi.org/10.1007/s00607-013-0316-2
[121]
Sundar, S., Singh, A. and Rossi, A. (2010) An Artificial Bee Colony Algorithm for the 0-1 Multidimensional Knapsack Problem. Proceedings of the International Conference on Contemporary Computing, Noida, 9-11 August 2010, 141-151. https://doi.org/10.1007/978-3-642-14834-7_14
[122]
Ji, J., Wei, H., Liu, C. and Yin, B. (2013) Artificial Bee Colony Algorithm Merged with Pheromone Communication Mechanism for the 0-1 Multidimensional Knapsack Problem. Mathematical Problems in Engineering, 2013, 13. https://doi.org/10.1155/2013/676275
[123]
Bole, A.V. and Kumar, R. (2017) Multidimensional 0-1 Knapsack Using Directed Bee Colony Algorithm. Proceedings of the IEEE International Conference on Intelligent Techniques in Control, Optimization and Signal Processing, Srivilliputhur, 23-25 March 2017, 1-10.
[124]
Sabba, S. and Chikhi, S. (2014) A Discrete Binary Version of Bat Algorithm for Multidimensional Knapsack Problem. International Journal of Bio-Inspired Computation, 6, 140-152. https://doi.org/10.1504/IJBIC.2014.060598
[125]
Gong, Q., Zhou, Y. and Luo, Q. (2011) Hybrid Artificial Glowworm Swarm Optimization Algorithm for Solving Multidimensional Knapsack Problem. Procedia Engineering, 15, 2880-2884. https://doi.org/10.1016/j.proeng.2011.08.542
[126]
Azad, M.A.K., Rocha, A.M.A. and Fernandes, E.M. (2014) Improved Binary Artificial Fish Swarm Algorithm for the 0-1 Multidimensional Knapsack Problems. Swarm and Evolutionary Computation, 14, 66-75. https://doi.org/10.1016/j.swevo.2013.09.002
[127]
Azad, M.A.K., Rocha, A.M.A. and Fernandes, E.M. (2012) Solving Multidimensional 0-1 Knapsack Problem with an Artificial Fish Swarm Algorithm. Proceedings of the International Conference on Computational Science and Its Applications, Salvador de Bahia, 18-21 June 2012, 72-86.
[128]
Azad, M.A.K., Rocha, A.M.A. and Fernandes, E.M. (2015) Solving Large 0-1 Multidimensional Knapsack Problems by a New Simplified Binary Artificial Fish Swarm Algorithm. Journal of Mathematical Modelling and Algorithms in Operations Research, 14, 313-330. https://doi.org/10.1007/s10852-015-9275-2
[129]
Meng, T., Duan, J.H. and Pan, Q.K. (2017) An Improved Migrating Birds Optimization for Solving the Multidimensional Knapsack Problem. Proceedings of the 29th IEEE Chinese Control and Decision Conference, Chongqing, 28-30 May 2017, 4698-4703.
Baykasoğlu, A. and Ozsoydan, F.B. (2014) An Improved Firefly Algorithm for Solving Dynamic Multidimensional Knapsack Problems. Expert Systems with Applications, 41, 3712-3725. https://doi.org/10.1016/j.eswa.2013.11.040
[132]
Zouache, D., Nouioua, F. and Moussaoui, A. (2016) Quantum-Inspired Firefly Algorithm with Particle Swarm Optimization for Discrete Optimization Problems. Soft Computing, 20, 2781-2799. https://doi.org/10.1007/s00500-015-1681-x
[133]
Meng, T. and Pan, Q.K. (2017) An Improved Fruit Fly Optimization Algorithm for Solving the Multidimensional Knapsack Problem. Applied Soft Computing, 50, 79-93. https://doi.org/10.1016/j.asoc.2016.11.023
[134]
Abdel-Basset, M., El-Shahat, D., El-Henawy, I. and Sangaiah, A.K. (2017) A Modified Flower Pollination Algorithm for the Multidimensional Knapsack Problem: Human-Centric Decision Making. Soft Computing, 22, 19.
[135]
Kong, X., Gao, L., Ouyang, H. and Li, S. (2015) Solving Large-Scale Multidimensional Knapsack Problems with a New Binary Harmony Search Algorithm. Computers & Operations Research, 63, 7-22. https://doi.org/10.1016/j.cor.2015.04.018
[136]
Liu, J., Wu, C., Cao, J., Wang, X. and Teo, K.L. (2016) A Binary Differential Search Algorithm for the 0-1 Multidimensional Knapsack Problem. Applied Mathematical Modelling, 40, 9788-9805. https://doi.org/10.1016/j.apm.2016.06.002
[137]
Tasgetiren, M.F., Pan, Q.K., Kizilay, D. and Suer, G. (2015) A Differential Evolution Algorithm with Variable Neighborhood Search for Multidimensional Knapsack Problem. Proceedings of the IEEE Congress on Evolutionary Computation, Sendai, 25-28 May 2015, 2797-2804.
[138]
Peng, H., Wu, Z., Shao, P. and Deng, C. (2016) Dichotomous Binary Differential Evolution for Knapsack Problems. Mathematical Problems in Engineering, 2016, 12. https://doi.org/10.1155/2016/5732489
[139]
Wang, L., Yang, R., Ni, H., Ye, W., Fei, M. and Pardalos, P.M. (2015) A Human Learning Optimization Algorithm and Its Application to Multi-Dimensional Knapsack Problems. Applied Soft Computing, 34, 736-743. https://doi.org/10.1016/j.asoc.2015.06.004
[140]
Bonyadi, M.R. and Li, X. (2012) A New Discrete Electromagnetism-Based Meta-Heuristic for Solving the Multidimensional Knapsack Problem Using Genetic Operators. Operational Research, 12, 229-252. https://doi.org/10.1007/s12351-010-0084-0
[141]
Hanafi, S. and Wilbaut, C. (2008) Scatter Search for the 0-1 Multidimensional Knapsack Problem. Journal of Mathematical Modelling and Algorithms, 7, 143-159. https://doi.org/10.1007/s10852-008-9078-9
[142]
Vianna, D.S., Montané, F.A.T., Meza, E.B.M. and Martins, C.B. (2014) A Memory-Based Grasp Heuristic for the Multiobjective Multidimensional Knapsack Problem. International Journal of Latest Research in Science and Technology, 3, 186-194.
[143]
Feo, T.A., Resende, M.G. and Smith, S.H. (1994) A Greedy Randomized Adaptive Search Procedure for Maximum Independent set. Operations Research, 42, 860-878. https://doi.org/10.1287/opre.42.5.860
[144]
Lust, T. and Teghem, J. (2010) Two-Phase Pareto Local Search for the Biobjective Traveling Salesman Problem. Journal of Heuristics, 16, 475-510. https://doi.org/10.1007/s10732-009-9103-9
[145]
Ahuja, R.K., Ergun, O., Orlin, J.B. and Punnen, A.P. (2002) A Survey of Very Large-Scale Neighborhood Search Techniques. Discrete Applied Mathematics, 123, 75-102. https://doi.org/10.1016/S0166-218X(01)00338-9
[146]
Lust, T. and Teghem, J. (2008) Memots: A Memetic Algorithm Integrating Tabu Search for Combinatorial Multiobjective Optimization. RAIRO Operations Research, 42, 3-33. https://doi.org/10.1051/ro:2008003
[147]
Li, V.C., Liang, Y.C., Sun, Y.Y. and Chen, Y.S. (2012) A Scatter Search Method for the Multidimensional Knapsack Problem with Generalized Upper Bound Constraints. Journal of the Chinese Institute of Industrial Engineers, 29, 559-571. https://doi.org/10.1080/10170669.2012.743643
[148]
Kenneth, Z., Lu, Y. and Vasko, F.J. (2015) Teacher Training Enhances the Teaching-Learning-Based Optimization Metaheuristic when Used to Solve Multiple-Choice Multidimensional Knapsack Problems. International Journal of Metaheuristics, 4, 268-293.
[149]
Wang, L., Wang, S.Y. and Xu, Y. (2012) An Effective Hybrid EDA-Based Algorithm for Solving Multidimensional Knapsack Problem. Expert Systems with Applications, 39, 5593-5599. https://doi.org/10.1016/j.eswa.2011.11.058
[150]
Yuan, Q. and Yang, Z.X. (2016) A Weight-Coded Evolutionary Algorithm for the Multidimensional Knapsack Problem. Advances in Pure Mathematics, 6, 659-675. https://doi.org/10.4236/apm.2016.610055
[151]
Deane, J. and Agarwal, A. (2012) Neural Metaheuristics for the Multidimensional Knapsack Problem. Technical Report. https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=2ah UKEwjXqfeeks_dAhWSxoUKHcU_CvkQFjAAegQIARAC&url=https%3A%2F%2Fpdfs.se manticscholar.org%2F2f57%2F1ae946c865b4e98e0a980c31806a686b4621.pdf &usg=AOvVaw1vNuVhp9pjBPBFnlEkyHQc
[152]
De Almeida Dantas, B. and Cáceres, E.N. (2016) Sequential and Parallel Hybrid Approaches of Augmented Neural Networks and GRASP for the 0-1 Multidimensional Knapsack Problem. Proceedings of the International Conference on Computational Science and Its Applications, Beijing, 4-7 July 2016, 207-222.
[153]
Vianna, D.S. and Vianna, M.D.F.D. (2013) Local Search-Based Heuristics for the Multiobjective Multidimensional Knapsack Problem. Production, 23, 478-487. https://doi.org/10.1590/S0103-65132012005000081
[154]
Alves, M.J. and Almeida, M.M. (2007) A Multiobjective Tchebycheff Based Genetic Algorithm for the Multidimensional Knapsack Problem. Computers & Operations Research, 34, 3458-3470. https://doi.org/10.1016/j.cor.2006.02.008
[155]
Jaskiewicz, A. (2002) On the Performance of Multiple Objective Genetic Local Search on the 0/1 Knapsack Problem: A Comparative Experiment. IEEE Transactions on Evolutionary Computation, 6, 402-412. https://doi.org/10.1109/TEVC.2002.802873
[156]
Zitzler, E., Laumanns, M. and Thiele, L. (2001) SPEA2: Improving the Strength Pareto Evolutionary Algorithm. Research Report.
[157]
Moraga, R.J., DePuy, G.W. and Whitehouse, G.E. (2004) Meta-RaPS Approach for the 0-1 Multidimensional Knapsack Problem. Computers & Industrial Engineering, 48, 83-96. https://doi.org/10.1016/j.cie.2004.02.008
[158]
Arin, A. and Rabadi, G. (2016) Local Search versus Path Relinking in Metaheuristics: Redesigning Meta-RaPS with Application to the Multidimensional Knapsack Problem. Applied Soft Computing, 46, 317-327. https://doi.org/10.1016/j.asoc.2016.05.016
[159]
Arin, A. and Rabadi, G. (2017) Integrating Estimation of Distribution Algorithms versus Q-Learning into Meta-RaPS for Solving the 0-1 Multidimensional Knapsack Problem. Computers & Industrial Engineering, 112, 706-720. https://doi.org/10.1016/j.cie.2016.10.022
[160]
Htiouech, S. and Alzaidi, A. (2017) Smart Agents for the Multidimensional Multi-Choice Knapsack Problem. International Journal of Computer Applications, 174, 5-9. https://doi.org/10.5120/ijca2017915404
[161]
Khalili-Damghani, K., Nojavan, M. and Tavana, M. (2013) Solving Fuzzy Multidimensional Multiple-Choice Knapsack Problems: The Multi-Start Partial Bound Enumeration Method versus the Efficient Epsilon-Constraint Method. Applied Soft Computing, 13, 1627-1638. https://doi.org/10.1016/j.asoc.2013.01.014
[162]
Mavrotas, G. (2009) Effective Implementation of the Epsi-lon-Constraint Method in Multi-Objective Mathematical Programming problems. Applied Mathematics and Computations, 213, 455-465. https://doi.org/10.1016/j.amc.2009.03.037
[163]
Gao, C., Lu, G., Yao, X. and Li, J. (2017) An Iterative Pseudo-Gap Enumeration Approach for the Multidimensional Multiple-Choice Knapsack Problem. European Journal of Operational Research, 260, 1-11. https://doi.org/10.1016/j.ejor.2016.11.042
[164]
Boussier, S., Vasquez, M., Vimont, Y., Hanafi, S. and Michelon, P. (2010) A Multi-Level Search Strategy for the 0-1 Multidimensional Knapsack Problem. Discrete Applied Mathematics, 158, 97-109. https://doi.org/10.1016/j.dam.2009.08.007
[165]
Sharafi, P., Askarian, M., Uz, M.E. and Abaci, H. (2017) Form Finding for Rectilinear Orthogonal Buildings through Charged System Search Algorithm. International Journal of Optimization in Civil Engineering, 7, 129-142.
[166]
Kaveh, A. and Talatahari, S. (2010) A Novel Heuristic Optimization Method: Charged System Search. ActaMechanica, 213, 267-289. https://doi.org/10.1007/s00707-009-0270-4
[167]
Urli, T. (2015) Hybrid Meta-Heuristics for Combinatorial Optimization. Ph.D. Thesis, University of Udine, Italy. https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja& uact=8&ved=2ahUKEwiaoIf8mc_dAhUM1hoKHebcBcAQFjAAegQIChAC&url=https%3A%2F% 2Fwww.a4cp.org%2Fsites%2Fdefault%2Ffiles%2Ftommaso_urli_-_hybrid_meta- heuristics_for_combinatorial_optimisation.pdf&usg=AOvVaw3JThZYEFS1Op5oLRPZ2IzX
