Article
LP relaxation and dynamic programming enhancing VNS for the multiple knapsack problem with setup
Malek Masmoudi,
Yassine Adouani,
Bassem Jarboui,
Corresponding Author
Malek Masmoudi
College of Engineering, University of Sharjah, Sharjah, UAE
Corresponding author.
Search for more papers by this authorYassine Adouani
Laboratory of Modeling and Optimization for Decisional, Industrial and Logistic Systems (MODILS), Faculty of Economics and Management Sciences of Sfax, University of Sfax, Sfax, Tunisia
Search for more papers by this authorMalek Masmoudi,
Yassine Adouani,
Bassem Jarboui,
Corresponding Author
Malek Masmoudi
College of Engineering, University of Sharjah, Sharjah, UAE
Corresponding author.
Search for more papers by this authorYassine Adouani
Laboratory of Modeling and Optimization for Decisional, Industrial and Logistic Systems (MODILS), Faculty of Economics and Management Sciences of Sfax, University of Sfax, Sfax, Tunisia
Search for more papers by this authorAbstract
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.
References
- Adouani, Y., Jarboui B., Masmoudi M., 2020. Efficient matheuristic for the generalised multiple knapsack problem with setup. European Journal of Industrial Engineering 14, 1–27.
- Adouani, Y., Jarboui B., Masmoudi, M., 2019. A matheuristic for the 0–1 generalised quadratic multiple knapsack problem. Optimization Letters 16, 37–58.
- Aïder, M., Gacem, O., Hifi, M., 2022. A hybrid population-based algorithm for the bi-objective quadratic multiple knapsack problem. Expert Systems with Applications 191, 116238.
- Akcay, Y., Li, H., Xu, S.H., 2007. Greedy algorithm for the general multidimensional knapsack problem. Annals of Operations Research 150, 17–29.
- 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 Research 25, 2, 637–666.
- Amiri, A., 2019. A Lagrangean based solution algorithm for the knapsack problem with setups. Expert System with Application 143, 113077.
- Amiri, A., Barkhi, R., 2020. A Lagrangean based solution algorithm for the multiple knapsack problem with setups. Computers & Industrial Engineering 153, 107089.
- Avci, M., Topaloglu, S., 2017. A multi-start iterated local search algorithm for the generalized quadratic multiple knapsack problem. Computers & Operations Research 83, 54–65.
- Bellman, R., 1957. Dynamic Programming. Princeton University Press, Princeton, NJ.
- 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.
- 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.
10.1007/978-3-030-80119-9_7 Google Scholar
- 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.
- 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 Research 203, 2, 484–493.
- Cacchiani, V., Lori, M., Locatelli, A., Martello, S. 2022a. Knapsack problems—an overview of recent advances. Part I: single knapsack problems. Computers & Operations Research 143, 105692,
- 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 Research 143, 105693.
- Chajakis, E., Guignard, M., 1994. Exact algorithms for the setup knapsack problem. INFOR 32, 124–142.
- Chebil, K., Khemakhem, M., 2015. A dynamic programming algorithm for the knapsack problem with setup. Computers & Operations Research 64, 40–50.
- Della, C. F., Salassa, F., Scatamacchia, R., 2017. An exact approach for the 0–1 knapsack problem with setups. Computers & Operations Research 80, 61–67.
- Dell'Amico, M., Delorme, M., Iori, M., Martello, S., 2019. Mathematical models and decomposition methods for the multiple knapsack problem. European Journal of Operational Research 274, 886–899.
- 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 Research 30, 6, 4061–4077.
- Fleszar, K., 2022. A branch-and-bound algorithm for the quadratic multiple knapsack problem. European Journal of Operational Research 298, 1, 89–98. https://doi.org/10.1016/j.ejor.2021.06.018
- Furini, F., Monaci, M., Traversi, E., 2018. Exact approaches for the knapsack problem with setups. Computers & Operations Research 90, 208–220.
- Hansen, P., Mladenović, N., Perez-Britos, D., 2001. Variable neighborhood decomposition search. Journal of Heuristics 7, 335–350.
- Hansen, P., Mladenovic, N., 2001. Variable neighborhood search: principles and applications. European Journal of Operational Research 130, 449–467.
- Horowitz, E., Sahni, S., 1974. Computing partitions with applications to the knapsack problem. Journal of ACM 21, 277–292.
- Khemakhem, M, Chebil, K., 2016. A tree search based combination heuristic for the knapsack problem with setup. Computers & Industrial Engineering 99, 280–286.
- 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
10.1007/978-3-540-24777-7_9 Google Scholar
- Kohli, R., Krishnamurti, R., 1992. A total-value greedy heuristic for the integer knapsack problem. Operations Letters 12, 65–71. https://doi.org/10.1007/978-3-540-24777-7_9
- Lahyani, R., Chebil, K., Khemakhem, M., Coelho, L.C., 2019. Matheuristics for solving the multiple knapsack problem with setup. Computers & industrial engineering 129, 76-89.
- 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 Research 274, 35–48.
- Lin, E., 1998. A bibliographical survey on some well-known non-standard knapsack problems. INFOR 36, 274–317.
- Martello, S., Toth, P., 1977. An upper bound for the zero-one knapsack problem and a branch and bound algorithm. European Journal of Operational Research 1, 169–175.
10.1016/0377-2217(77)90024-8 Google Scholar
- Martello, S., Toth, P., 1990. Problems: Algorithms and Computer Implementations. John Wiley & Sons, New York.
- Mladenovic, N., Hansen, P., 1997. Variable neighborhood search. Computers & Operations Research, 24, 1097–1100.
- Michel, S., Perrot, N., Vanderbeck, F., 2009. Knapsack problems with setups. European Journal of Operational Research 196, 909–918.
- Pferschy, U., Scatamacchia, R., 2017. Improved dynamic programming and approximation results for the knapsack problem with setups. International Transactions in Operational Research 25, 667–682.
- Pisinger, D., 1994. A minimal algorithm for the 0–1 knapsack problem. Operations Research 45, 758–767.
10.1287/opre.45.5.758 Google Scholar
- Plateau, G., Elkihel, M., 1985. A hybrid method for the 0–1 knapsack problem. Methods of Operations Research 49, 277–293.
- 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 Research 191, 1004–1022.
- Puchinger, J., Raidl, G.R., Pferschy, U., 2006. The core concept for the multidimensional knapsack problem. In J. Gottlieb, G.R. Raidl (eds) Evolutionary Computation in Combinatorial Optimization, EvoCOP 2006. Springer, Berlin, Heidelberg, pp. 195–208.
- Saraç, T., Sipahioglu, A., 2014. Generalized quadratic multiple knapsack problem and two solution approaches. Computers & Operations Research 43, 78–89.
- Sur, G., Ryu, S.Y., Kim, J., Lim, H. 2022. A deep reinforcement learning-based scheme for solving multiple knapsack problems. Applied Sciences 12, 3068.
- Toth, P., 1980. Dynamic programming algorithms for the zero-one knapsack problem. Computing, 25, 29–45.
- Wang, X.Z., Yichao, H., 2017. Evolutionary algorithms for knapsack problems. Journal of Software, 28, 1–16.
- Yang, Y., Bulfin, R., 2009. An exact algorithm for the knapsack problem with setup. International Journal of Operational Research 5, 280–291.
10.1504/IJOR.2009.025197 Google Scholar
- Yang, Y., 2006. Knapsack problems with setup. PhD thesis, Auburn University, Auburn, AL.
