An effective hybrid search method for the quadratic knapsack problem with conflict graphs

References

• Aisopos, F., Tserpes, K., & Varvarigou, T. (2013). Resource management in software as a service using the knapsack problem model. International Journal of Production Economics, 141(2), 465–477. https://doi.org/10.1016/j.ijpe.2011.12.011
   Web of Science ®Google Scholar
• Alozie, G. U., Arulselvan, A., Akartunal I, K., & Pasiliao, E. L. Jr., (2022). A heuristic approach for the distance-based critical node detection problem in complex networks. Journal of the Operational Research Society, 73(6), 1347–1361. https://doi.org/10.1080/01605682.2021.1913078
   Web of Science ®Google Scholar
• Billionnet, A., & Soutif, É. (2004). An exact method based on Lagrangian decomposition for the quadratic knapsack problem. European Journal of Operational Research, 157(3), 565–575. https://doi.org/10.1016/S0377-2217(03)00244-3
   Web of Science ®Google Scholar
• Carrasco, J., García, S., Rueda, M. M., Das, S., & Herrera, F. (2020). Recent trends in the use of statistical tests for comparing swarm and evolutionary computing algorithms: Practical guidelines and a critical review. Swarm and Evolutionary Computation, 54, 100665. https://doi.org/10.1016/j.swevo.2020.100665
   Web of Science ®Google Scholar
• 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
   Web of Science ®Google Scholar
• Chih, M. (2018). Three pseudo-utility ratio-inspired particle swarm optimization with local search for multidimensional knapsack problem. Swarm and Evolutionary Computation, 39, 279–296. https://doi.org/10.1016/j.swevo.2017.10.008
   Web of Science ®Google Scholar
• Chih, M. (2023). Stochastic stability analysis of particle swarm optimization with pseudo random number assignment strategy. European Journal of Operational Research, 305(2), 562–593. https://doi.org/10.1016/j.ejor.2022.06.009
   Web of Science ®Google Scholar
• Coniglio, S., Furini, F., & San Segundo, P. (2021). A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts. European Journal of Operational Research, 289(2), 435–455. https://doi.org/10.1016/j.ejor.2020.07.023
   Web of Science ®Google Scholar
• Constantino, O. H., & Segura, C. (2022). A parallel memetic algorithm with explicit management of diversity for the job shop scheduling problem. Applied Intelligence, 52(1), 141–153. https://doi.org/10.1007/s10489-021-02406-2
   Web of Science ®Google Scholar
• Dahmani, I., & Hifi, M. (2021). A modified descent method-based heuristic for binary quadratic knapsack problems with conflict graphs. Annals of Operations Research, 298(1-2), 125–147. https://doi.org/10.1007/s10479-019-03290-3
   Web of Science ®Google Scholar
• Dahmani, I., Hifi, M., Saadi, T., & Yousef, L. (2020). A swarm optimization-based search algorithm for the quadratic knapsack problem with conflict graphs. Expert Systems with Applications, 148, 113224. https://doi.org/10.1016/j.eswa.2020.113224
   Web of Science ®Google Scholar
• Glover, F., & Laguna, M. (1998). Tabu search. In Du, D. Z., & Pardalos, P. M. (Eds.), Handbook of combinatorial optimization (pp. 2093–2229). Springer.
   Google Scholar
• Hao, J. K. (2012). Memetic algorithms in discrete optimization. In F. Neri, C. Cotta, and P. Moscato (Eds.), Handbook of memetic algorithms, studies in computational intelligence, Vol 379 (pp. 73–94). Springer.
   Google Scholar
• Hifi, M., & Michrafy, M. (2006). A reactive local search-based algorithm for the disjunctively constrained knapsack problem. Journal of the Operational Research Society, 57(6), 718–726. https://doi.org/10.1057/palgrave.jors.2602046
   Web of Science ®Google Scholar
• Hifi, M., & Michrafy, M. (2007). Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem. Computers & Operations Research, 34(9), 2657–2673. https://doi.org/10.1016/j.cor.2005.10.004
   Web of Science ®Google Scholar
• Kellerer, H., Pferschy, U., & Pisinger, D. (2004). Multidimensional Knapsack Problems. In Knapsack problems (pp. 235–283). Springer.
   Google Scholar
• Lai, X., & Hao, J. K. (2016). Iterated variable neighborhood search for the capacitated clustering problem. Engineering Applications of Artificial Intelligence, 56, 102–120. https://doi.org/10.1016/j.engappai.2016.08.004
   Web of Science ®Google Scholar
• Li, Z., Tang, L., & Liu, J. (2022). A memetic algorithm based on probability learning for solving the multidimensional knapsack problem. IEEE Transactions on Cybernetics, 52(4), 2284–2299. https://doi.org/10.1109/TCYB.2020.3002495
   PubMed Web of Science ®Google Scholar
• López-Ibáñez, M., Dubois-Lacoste, J., Cáceres, L. P., Birattari, M., & Stützle, T. (2016). The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, 3, 43–58. https://doi.org/10.1016/j.orp.2016.09.002
   Web of Science ®Google Scholar
• Lü, Z., & Hao, J. K. (2010). A memetic algorithm for graph coloring. European Journal of Operational Research, 203(1), 241–250. https://doi.org/10.1016/j.ejor.2009.07.016
   Web of Science ®Google Scholar
• Lü, Z., Hao, J. K., & Glover, F. (2011). Neighborhood analysis: A case study on curriculum-based course timetabling. Journal of Heuristics, 17(2), 97–118. https://doi.org/10.1007/s10732-010-9128-0
   Web of Science ®Google Scholar
• Moscato, P. (1999). Memetic algorithms: A short introduction. In D. Corne, M. Dorigo, F. Glover, D. Dasgupta, R. Poli, & K. V. Price (eds.), New ideas in optimization (pp. 219–234). McGraw-Hill Ltd.
   Google Scholar
• Neri, F., & Cotta, C. (2012). Memetic algorithms and memetic computing optimization: A literature review. Swarm and Evolutionary Computation, 2, 1–14. https://doi.org/10.1016/j.swevo.2011.11.003
   Web of Science ®Google Scholar
• Perboli, G., Gobbato, L., & Perfetti, F. (2014). Packing problems in transportation and supply chain: New problems and trends. Procedia - Social and Behavioral Sciences, 111, 672–681. https://doi.org/10.1016/j.sbspro.2014.01.101
   Google Scholar
• Pferschy, U., & Schauer, J. (2017). Approximation of knapsack problems with conflict and forcing graphs. Journal of Combinatorial Optimization, 33(4), 1300–1323. https://doi.org/10.1007/s10878-016-0035-7
   Web of Science ®Google Scholar
• Salem, M. B., Hanafi, S., Taktak, R., & Abdallah, H. B. (2017). Probabilistic Tabu search with multiple neighborhoods for the Disjunctively Constrained Knapsack Problem. RAIRO - Operations Research, 51(3), 627–637. https://doi.org/10.1051/ro/2016049
   Web of Science ®Google Scholar
• Shi, X., Wu, L., & Meng, X. (2017). A new optimization model for the sustainable development: Quadratic knapsack problem with conflict graphs. Sustainability, 9(2), 236. https://doi.org/10.3390/su9020236
   Web of Science ®Google Scholar
• Spencer, K. Y., Tsvetkov, P. V., & Jarrell, J. J. (2019). A greedy memetic algorithm for a multiobjective dynamic bin packing problem for storing cooling objects. Journal of Heuristics, 25(1), 1–45. https://doi.org/10.1007/s10732-018-9382-0
   Web of Science ®Google Scholar
• Van der Merwe, D. J., & Hattingh, J. M. (2006). Tree knapsack approaches for local access network design. European Journal of Operational Research, 174(3), 1968–1978. https://doi.org/10.1016/j.ejor.2005.03.043
   Web of Science ®Google Scholar
• Wei, Z., & Hao, J. K. (2021). A threshold search based memetic algorithm for the disjunctively constrained knapsack problem. Computers & Operations Research, 136, 105447. https://doi.org/10.1016/j.cor.2021.105447
   Web of Science ®Google Scholar
• Wei, Z., Hao, J. K., Ren, J., & Glover, F. (2023). Responsive strategic oscillation for solving the disjunctively constrained knapsack problem. European Journal of Operational Research, 309(3), 993–1009. https://doi.org/10.1016/j.ejor.2023.02.009
   Web of Science ®Google Scholar
• Wu, Q., Hao, J. K., & Glover, F. (2012). Multi-neighborhood tabu search for the maximum weight clique problem. Annals of Operations Research, 196(1), 611–634. https://doi.org/10.1007/s10479-012-1124-3
   Web of Science ®Google Scholar
• Yamada, T., Kataoka, S., & Watanabe, K. (2002). Heuristic and exact algorithms for the disjunctively constrained knapsack problem. Information Processing Society of Japan Journal, 43(9), 2864–2870.
   Google Scholar
• Zhou, F., He, Y., Ma, P., Lim, M. K., & Pratap, S. (2022). Capacitated disassembly scheduling with random demand and operation time. Journal of the Operational Research Society, 73(6), 1362–1378. https://doi.org/10.1080/01605682.2021.1911603
   Web of Science ®Google Scholar
• Zhou, Y., Hao, J. K., & Duval, B. (2022). Frequent pattern-based search: A case study on the quadratic assignment problem. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 52(3), 1503–1515. https://doi.org/10.1109/TSMC.2020.3027860
   Web of Science ®Google Scholar
• Zobolas, G. I., Tarantilis, C. D., & Ioannou, G. (2009). A hybrid evolutionary algorithm for the job shop scheduling problem. Journal of the Operational Research Society, 60(2), 221–235. https://doi.org/10.1057/palgrave.jors.2602534
   Web of Science ®Google Scholar