LP relaxation and dynamic programming enhancing VNS for the multiple knapsack problem with setup. (English) Zbl 07797338
Summary: We consider the multiple knapsack problem (KP) with setup (MKPS), which is an extension of the KP with setup (KPS). We propose a new solving approach denoted by LP&DP-VNS that combines linear programming (LP) relaxation and dynamic programming (DP) to enhance variable neighborhood search (VNS). The LP&DP-VNS is tailored to the characteristics of the MKPS and reduced to LP&DP to solve the KPS. The approach is tested on 200 KPS and 360 MKPS benchmark instances. Computational experiments show the effectiveness of the LP&DP-VNS, compared to integer programming (using CPLEX) and the best state-of-the-art algorithms. It reaches 299/342 optimal solutions and 316/318 best-known solutions and provides 127 new best solutions. An additional computational study shows that the LP&DP-VNS scales up extremely well, solving optimally and near-optimally very large instances with up 200 families and 300,000 items in a reasonable amount of time.
© 2022 The Authors. International Transactions in Operational Research © 2022 International Federation of Operational Research Societies.
© 2022 The Authors. International Transactions in Operational Research © 2022 International Federation of Operational Research Societies.
MSC:
| 90-XX | Operations research, mathematical programming |
Keywords:
metaheuristics; LP relaxation; dynamic programming; variable neighborhood search; multiple knapsack problem with setupReferences:
| [1] | Adouani, Y., JarbouiB., MasmoudiM., 2020. Efficient matheuristic for the generalised multiple knapsack problem with setup. European Journal of Industrial Engineering14, 1-27. |
| [2] | Adouani, Y., JarbouiB., Masmoudi, M., 2019. A matheuristic for the 0-1 generalised quadratic multiple knapsack problem. Optimization Letters16, 37-58. · Zbl 1483.90127 |
| [3] | Aïder, M., Gacem, O., Hifi, M., 2022. A hybrid population‐based algorithm for the bi‐objective quadratic multiple knapsack problem. Expert Systems with Applications191, 116238. |
| [4] | Akcay, Y., Li, H., Xu, S.H., 2007. Greedy algorithm for the general multidimensional knapsack problem. Annals of Operations Research150, 17-29. · Zbl 1144.90466 |
| [5] | Al‐Maliky, F., Hifi, M., Mhalla, H., 2018. Sensitivity analysis of the setup knapsack problem to perturbation of arbitrary profits or weights. International Transactions in Operational Research25, 2, 637-666. · Zbl 1391.90500 |
| [6] | Amiri, A., 2019. A Lagrangean based solution algorithm for the knapsack problem with setups. Expert System with Application143, 113077. |
| [7] | Amiri, A., Barkhi, R., 2020. A Lagrangean based solution algorithm for the multiple knapsack problem with setups. Computers & Industrial Engineering153, 107089. |
| [8] | Avci, M., Topaloglu, S., 2017. A multi‐start iterated local search algorithm for the generalized quadratic multiple knapsack problem. Computers & Operations Research83, 54-65. · Zbl 1458.90534 |
| [9] | Bellman, R., 1957. Dynamic Programming. Princeton University Press, Princeton, NJ. · Zbl 0077.13605 |
| [10] | Boukhari, S., Dahmani, I., Hifi, M.2020. Local branching strategy‐based method for the knapsack problem with setup. Proceedings of the 4th International Conference on Artificial Intelligence, Soft Computing And Applications, CS & IT‐CSCP, November 28-29, 2020, Dubai, UAE, pp. 65-75. |
| [11] | Boukhari, S., Dahmani, I., Hifi, M.2022a. Computational power of a hybrid algorithm for solving the multiple knapsack problem with setup. Intelligent Computing. Springer, Cham. 154-168. |
| [12] | Boukhari, S., Dahmani, I., Hifi, M.2022b. Effect of the local branching strategy on the descent method: the case of the generalized multiple knapsack with setup. Computers & Industrial Engineering 165, 107934. |
| [13] | Burke, E.K., Li, J., Qu, R., 2010. A hybrid model of integer programming and variable neighborhood search for highly‐constrained nurse rostering problems. European Journal of Operational Research203, 2, 484-493. · Zbl 1177.90356 |
| [14] | Cacchiani, V., Lori, M., Locatelli, A., Martello, S.2022a. Knapsack problems—an overview of recent advances. Part I: single knapsack problems. Computers & Operations Research143, 105692, · Zbl 1512.90189 |
| [15] | Cacchiani, V., Lori, M., Locatelli, A., Martello, S.2022b. Knapsack problems-an overview of recent advances. Part II: multiple, multidimensional, and quadratic knapsack problems. Computers & Operations Research143, 105693. · Zbl 1512.90190 |
| [16] | Chajakis, E., Guignard, M., 1994. Exact algorithms for the setup knapsack problem. INFOR32, 124-142. · Zbl 0811.90072 |
| [17] | Chebil, K., Khemakhem, M., 2015. A dynamic programming algorithm for the knapsack problem with setup. Computers & Operations Research64, 40-50. · Zbl 1349.90634 |
| [18] | Della, C. F., Salassa, F., Scatamacchia, R., 2017. An exact approach for the 0-1 knapsack problem with setups. Computers & Operations Research80, 61-67. · Zbl 1391.90513 |
| [19] | Dell’Amico, M., Delorme, M., Iori, M., Martello, S., 2019. Mathematical models and decomposition methods for the multiple knapsack problem. European Journal of Operational Research274, 886-899. · Zbl 1430.90480 |
| [20] | Dellinger, A., Lu, Y., Song, M.S, Vasko, F.J.2022. Simple strategies that generate bounded solutions for the multiple‐choice multi‐dimensional knapsack problem: a guide for OR practitioners. International Transactions in Operational Research30, 6, 4061-4077. · Zbl 07745356 |
| [21] | Fleszar, K., 2022. A branch‐and‐bound algorithm for the quadratic multiple knapsack problem. European Journal of Operational Research298, 1, 89-98. https://doi.org/10.1016/j.ejor.2021.06.018 · Zbl 1490.90242 · doi:10.1016/j.ejor.2021.06.018 |
| [22] | Furini, F., Monaci, M., Traversi, E., 2018. Exact approaches for the knapsack problem with setups. Computers & Operations Research90, 208-220. · Zbl 1391.90516 |
| [23] | Hansen, P., Mladenović, N., Perez‐Britos, D., 2001. Variable neighborhood decomposition search. Journal of Heuristics7, 335-350. · Zbl 1041.68623 |
| [24] | Hansen, P., Mladenovic, N., 2001. Variable neighborhood search: principles and applications. European Journal of Operational Research130, 449-467. · Zbl 0981.90063 |
| [25] | Horowitz, E., Sahni, S., 1974. Computing partitions with applications to the knapsack problem. Journal of ACM21, 277-292. · Zbl 0329.90046 |
| [26] | Khemakhem, M, Chebil, K., 2016. A tree search based combination heuristic for the knapsack problem with setup. Computers & Industrial Engineering99, 280-286. |
| [27] | Kellerer, H., Pferschy, U., Pisinger, D., 2004. Multidimensional knapsack problems. In Knapsack Problems. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24777-7_9 · Zbl 1103.90003 · doi:10.1007/978-3-540-24777-7_9 |
| [28] | Kohli, R., Krishnamurti, R., 1992. A total‐value greedy heuristic for the integer knapsack problem. Operations Letters12, 65-71. https://doi.org/10.1007/978-3-540-24777-7_9 · Zbl 0757.90061 · doi:10.1007/978-3-540-24777-7_9 |
| [29] | Lahyani, R., Chebil, K., Khemakhem, M., Coelho, L.C., 2019. Matheuristics for solving the multiple knapsack problem with setup. Computers & industrial engineering129, 76‐89. |
| [30] | Lai, X., Hao, J.‐K., Yue, D., 2019. Two‐stage solution‐based tabu search for the multi‐demand multidimensional knapsack problem. European Journal of Operational Research274, 35-48. · Zbl 1430.90493 |
| [31] | Lin, E., 1998. A bibliographical survey on some well‐known non‐standard knapsack problems. INFOR36, 274-317. · Zbl 07677573 |
| [32] | Martello, S., Toth, P., 1977. An upper bound for the zero‐one knapsack problem and a branch and bound algorithm. European Journal of Operational Research1, 169-175. · Zbl 0374.90050 |
| [33] | Martello, S., Toth, P., 1990. Problems: Algorithms and Computer Implementations. John Wiley & Sons, New York. · Zbl 0708.68002 |
| [34] | Mladenovic, N., Hansen, P., 1997. Variable neighborhood search. Computers & Operations Research, 24, 1097-1100. · Zbl 0889.90119 |
| [35] | Michel, S., Perrot, N., Vanderbeck, F., 2009. Knapsack problems with setups. European Journal of Operational Research196, 909-918. · Zbl 1176.90175 |
| [36] | Pferschy, U., Scatamacchia, R., 2017. Improved dynamic programming and approximation results for the knapsack problem with setups. International Transactions in Operational Research25, 667-682. · Zbl 1391.90531 |
| [37] | Pisinger, D., 1994. A minimal algorithm for the 0-1 knapsack problem. Operations Research45, 758-767. · Zbl 0902.90126 |
| [38] | Plateau, G., Elkihel, M., 1985. A hybrid method for the 0-1 knapsack problem. Methods of Operations Research49, 277-293. · Zbl 0564.90037 |
| [39] | Prandtstetter, M., Raidl, G.R., 2008. An integer linear programming approach and a hybrid variable neighborhood search for the car sequencing problem. European Journal of Operational Research191, 1004-1022. · Zbl 1156.90321 |
| [40] | Puchinger, J., Raidl, G.R., Pferschy, U., 2006. The core concept for the multidimensional knapsack problem. In Gottlieb, J. (ed.), Raidl, G.R. (ed.) (eds) Evolutionary Computation in Combinatorial Optimization, EvoCOP 2006. Springer, Berlin, Heidelberg, pp. 195-208. · Zbl 1401.90198 |
| [41] | Saraç, T., Sipahioglu, A., 2014. Generalized quadratic multiple knapsack problem and two solution approaches. Computers & Operations Research43, 78-89. · Zbl 1348.90555 |
| [42] | Sur, G., Ryu, S.Y., Kim, J., Lim, H.2022. A deep reinforcement learning‐based scheme for solving multiple knapsack problems. Applied Sciences12, 3068. |
| [43] | Toth, P., 1980. Dynamic programming algorithms for the zero‐one knapsack problem. Computing, 25, 29-45. · Zbl 0431.90076 |
| [44] | Wang, X.Z., Yichao, H., 2017. Evolutionary algorithms for knapsack problems. Journal of Software, 28, 1-16. · Zbl 1389.90271 |
| [45] | Yang, Y., Bulfin, R., 2009. An exact algorithm for the knapsack problem with setup. International Journal of Operational Research5, 280-291. · Zbl 1169.90485 |
| [46] | Yang, Y., 2006. Knapsack problems with setup. PhD thesis, Auburn University, Auburn, AL. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
