Abstract
The discounted knapsack problem (DKP) is an NP-hard combinatorial optimization problem that has gained much attention recently. Due to its high complexity, the usual solution combines a global search algorithm with a greedy local search algorithm to repair candidate solutions. The current greedy algorithms use a heuristic that ignores the items already in a candidate solution. This paper presents a new greedy algorithm for DKP that uses an expanded set of operators and better heuristics that are more effective at considering the selected items. Experimental results show that the proposed greedy algorithm has superior performance to three well-known greedy algorithms for DKP, both when operating independently and when combined with global search algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Cacchiani, V., Iori, M., Locatelli, A., Martello, S.: Knapsack problems - an overview of recent advances. Part I: single knapsack problems. Comput. Oper. Res. 143, 105692 (2022)
Dang, B.T., Truong, T.K.: Binary salp swarm algorithm for discounted \(\{0-1\}\) knapsack problem. PLOS ONE 17(4), 1–28 (2022)
Dantzig, G.B.: Discrete-variable extremum problems. Oper. Res. 5(2), 266–288 (1957)
Emerson, P.: The original Borda count and partial voting. Social Choice Welfare 40(2), 353–358 (2013)
Guldan, B.: Heuristic and exact algorithms for discounted knapsack problems. University of Erlangen-Nürnberg, Germany (2007)
Haynes, W.: Wilcoxon Rank Sum Test, pp. 2354–2355. Springer, New York (2013). https://doi.org/10.1007/978-1-4419-9863-7_1185
He, Y.C., Wang, X.Z., Li, W.B., Zhang, X.L., Chen, Y.Y.: Research on genetic algorithms for the discounted \(\{0-1\}\) knapsack problem. Jisuanji Xuebao/Chin. J. Comput. 39(12), 2614–2630 (2016)
He, Y.C., Wang, X.Z., He, Y.L., Zhao, S.L., Li, W.B.: Exact and approximate algorithms for discounted \(\{0-1\}\) knapsack problem. Inf. Sci. 369(C), 634–647 (2016)
He, Y.: Four kinds of D\(\{0-1\}\)KP instances. ResearchGate (2019)
He, Y., Wang, X.: Group theory-based optimization algorithm for solving knapsack problems. Knowl.-Based Syst. 219, 104445 (2021)
He, Y., Wang, X., Gao, S.: Ring theory-based evolutionary algorithm and its application to D0–1 KP. Appl. Soft Comput. 77, 714–722 (2019)
Li, Y., He, Y., Liu, X., Guo, X., Li, Z.: A novel discrete whale optimization algorithm for solving knapsack problems. Appl. Intell. 50, 3350–3366 (2020)
Mathews, G.B.: On the partition of numbers. Proc. Lond. Math. Soc. s1–28(1), 486–490 (1896)
Nguyen, B.H., Xue, B., Andreae, P., Zhang, M.: A new binary particle swarm optimization approach: momentum and dynamic balance between exploration and exploitation. IEEE Trans. Cybern. 51(2), 589–603 (2021)
Nguyen, B.H., Xue, B., Zhang, M.: A survey on swarm intelligence approaches to feature selection in data mining. Swarm Evol. Comput. 54, 100663 (2020)
Sulaiman, A., Sadiq, M., Mehmood, Y., Akram, M., Ali, G.A.: Fitness-based acceleration coefficients binary particle swarm optimization to solve the discounted knapsack problem. Symmetry 14(6), 1208 (2022)
Truong, T.K.: different transfer functions for binary particle swarm optimization with a new encoding scheme for discounted \(\{0-1\}\) knapsack problem. Math. Prob. Eng. 2021 (2021)
Wilbaut, C., Hanafi, S., Coelho, I.M., Lucena, A.: The knapsack problem and its variants: formulations and solution methods. In: The Palgrave Handbook of Operations Research, pp. 105–151. Springer, Heidelberg (2022),https://doi.org/10.1007/978-3-030-96935-6_4
Wu, C., Zhao, J., Feng, Y., Lee, M.: Solving discounted \(\{0-1\}\) knapsack problems by a discrete hybrid teaching-learning-based optimization algorithm. Appl. Intell. 50, 1872–1888 (2020)
Zhu, H., He, Y.C., Wang, X., Tsang, E.C.: Discrete differential evolutions for the discounted \(\{0-1\}\) knapsack problem. Int. J. Bio-Inspired Comput. 10(4), 219–238 (2017)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Dang, B.T., Nguyen, B.H., Andreae, P. (2022). Operation-based Greedy Algorithm for Discounted Knapsack Problem. In: Aziz, H., Corrêa, D., French, T. (eds) AI 2022: Advances in Artificial Intelligence. AI 2022. Lecture Notes in Computer Science(), vol 13728. Springer, Cham. https://doi.org/10.1007/978-3-031-22695-3_45
Download citation
DOI: https://doi.org/10.1007/978-3-031-22695-3_45
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-22694-6
Online ISBN: 978-3-031-22695-3
eBook Packages: Computer ScienceComputer Science (R0)