Modified Greedy algorithm for Multidimensional Knapsack problem
Article Sidebar
Main Article Content
Abstract
The Knapsack Problem (KP) is a combinatorial optimization problem that involves selecting items to be placed in a backpack in order to maximize the total value without exceeding the specified capacity. This problem can be formulated as an integer linear programming problem (ILP). In this study, we focused on the multidimensional knapsack problem (MDKP), which has multiple constraints and is more complex to solve. We experimented with different methods for sorting the benefits and evaluated the results using the solver function in Microsoft Excel. We considered 49 examples of 0-1 binary and pure integer knapsack problems. The experimental results showed that selecting items based on modified benefit values (profit/weight ratio) yielded better results than using the difference in benefits, as measured by the mean absolute percentage error (MAPE) across all samples.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
The Journal of Science and Science Education (JSSE) retain the right of all articles published in JSSE. The coresponding author or the authorized person on behalf of the authors must send the complete Copyright Transfer Form to JSSE before any article get published in JSSE.
Copyright Transfer Form
The JSSE request the coresponding author or the authorized person on behalf of the authors upload the manuscript under the together with the Copyright Transfer Form under the supplementary data. The guidline for uploading both manuscript and Copyright Transfer Form is shown below:
1. Upload the manuscript in the sub-menu, Article Component > Article Text.
2. Upload the the Copyright Transfer Form in the sub-menu, Article Component > Other.
Download Copyright Transfer Form
References
Al Etawi, N. A., and Aburomman, F. T. (2020). 0/1 knapsack problem: greedy vs. Dynamic-programming. International Journal of Advanced Engineering and Management Research, 5(2), 1-10.
Akçay, Y., Li, H. and Xu, S. H. (2007). Greedy algorithm for the general multidimensional knapsack problem. Annals of operations research, 150, 17–29.
Berberler, M. E., Guler, A., and Nurıyev, U. G. (2013). A genetic algorithm to solve the multidimensional knapsack problem. Mathematical and Computational Applications, 18(3), 486-494.
Buayen, P. and Werapun, J. (2018). Parallel time–space reduction by unbiased filtering for solving the 0/1-Knapsack problem. Journal of Parallel and Distributed Computing, 122, 195 - 208.
Durmuş, B., Güneri, O. I. and Incekırık, A. (2019). Comparison of Classic and Greedy Heuristic Algorithm Results in Integer Problems. Mugla Journal of Science and Technology, 5(1), 34-42.
Glover, F. (1965). A multiphase-dual algorithm for the zero-one integer programming problem. Operation Research, 13, 879–919.
Hassan, R., Cohanim, B., De Weck, O., and Venter, G. (2005, April). A comparison of particle swarm optimization and the genetic algorithm. In 46th AIAA/ASME/ASCE/AHS/ASC structures, structural dynamics and materials conference (pp. 2005-1897). Texas.
Irmeilyana, I., Bangun, P. B. J. and Izzah, H. (2017). Solution of Multiple Constraints Knapsack Problem (MCKP) by using Branch and Bound and Greedy Algorithm. Journal of Modeling and Optimization, 9(2), 112-119.
Koohathongsumrit, N. and Luangpaiboon, P. (2021), An Integrated FAHP–ZODP Approach for Strategic Marketing Information System Project Selection. Managerial and Decision Economics, 43(6), 1792-1809.
Mingo López, L. F., Gómez Blas, N., and Arteta Albert, A. (2018). Multidimensional knapsack problem optimization using a binary particle swarm model with genetic operations. Soft Computing, 22, 2567-2582.
Minsan, P. (2021). Comparing Methods of Optimization in Solver of Microsoft Excel 2007 and 2019: A Case Study of Statistical Models, The journal of KMUTNB, 31(3), 496-511.
Mohammad, A., Saleh, O., and Abdeen, R. A. (2006). Occurrences algorithm for string searching based on brute-force algorithm. Journal of Computer Science, 2(1), 82-85.
Multiple Knapsack Problems (2023). Retrieved 5 September 2023, from OR-library: http://people.brunel.ac.uk/
Pisinger, D. (1999). Linear Time Algorithms for Knapsack Problems with Bounded Weights. Journal of Algorithms. 33(1), 1-14.
Puchinger, J., Raidl, G. R., and Pferschy, U. (2010). The multidimensional knapsack problem: Structure and algorithms. INFORMS Journal on Computing, 22(2), 250-265.
Sajjan, S. P., Roogi, R., Badiger, V. and Amaragatti, S. (2014). A New Approach to Solve Knapsack Problem. Oriental Journal of Computer Science & Technology, 7(2), 219.
Senju, S. and Toyada, Y. (1968). An approach to linear programming problems with 0–1 variables, Management Science, 15(4), 196–207.
Varnamkhasti, M. J. (2012). Overview of the Algorithms for Solving the Multidimensional Knapsack Problems. Advanced Studies in Biology, 4(1), 37-47.