A KNAPSACK OPTIMISATION MODEL TO DETERMINE THE REQUIRED ITEMS FOR AN ANNUAL DINNER
DOI:
https://doi.org/10.46754/umtjur.v4i2.278Keywords:
Knapsack problem, binary integer programming, optimization, items selectionAbstract
Many companies recognise the achievements and contributions of their employees throughout the year through annual dinners. Commonly, companies will allocate a certain amount of money to organise an annual dinner. However, planning such an event is not easy as the organising team needs to plan the event carefully according to the specified budget. This paper demonstrates how a binary knapsack problem approach is applied to help an insurance company select the required items for its annual dinner within the allocated budget. Two models were developed and solved using the LINGO 12.0 software. The first model was developed to determine the activities that will be selected based on the restriction of the total budget. The second model was developed to maximise staff preference on the selected items within the specified budget. The results of both models were compared and discussed. The item selection technique used in this study is for organisations with a limited budget.
References
Ahmad Saidi, A. A. I., Jing Yee, L., Xin Zhen, I. L., & Abdul-Rahman, S. (2021). Comparison between exact optimization and heuristics approaches for maximizing benefit of point redemption: A knapsack problem. Applied Mathematics and Computational Intelligence, 10(1), 78-86.
Bednarczuk, E. M., Miroforidis, J. & Pyzel, P. A. (2018). A multi-criteria approach to approximate solution of multiple-choice knapsack problem. Computational Optimization and Applications, 70(2018), 889–910. doi:org/ 10.1007/ s10589-018- 9988-z. DOI: https://doi.org/10.1007/s10589-018-9988-z
Blake, J. T., & Donald, J. (2002). Mount Sinai Hospital uses integer programming to allocate operating room time. Interfaces, 32(2), 63–73. DOI: https://doi.org/10.1287/inte.32.2.63.57
Earnshaw, S. R. & Dennett, S. L. (2003). Integer/ linear mathematical programming models: A tool for allocating healthcare resources. Pharmacoeconomics, 21(12), 839-51. doi: 10.2165/00019053-200321120-00001. DOI: https://doi.org/10.2165/00019053-200321120-00001
Fluschnik, T., Skowron, P., Triphaus, M., & Wilker, K. (2019). Fair Knapsack. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 1941- 1948. https://doi.org/10.1609/aaai. v33i01.33011941 DOI: https://doi.org/10.1609/aaai.v33i01.33011941
Gambrah, P. P. (2013). Plastic bags waste management using the Knapsack Model, case study; Trashy Bags Accra. International Journal of Scientific & Engineering Research, 4(5), 1913.
Haddadh, A. K., Yakhchali, S. H. & Jalili bal, Z. (2016). MCDM Techniques and Knapsack Approach for Project Selection Problem: A Case Study. International Journal of Humanities and Management Sciences, 4(4), 397-400.
Ichikawa, K., Yada, K., Nakachi, N., & T. Washio (2009). Optimization of budget allocation for TV advertising. Knowledge-Based Intelligent Information & Engineering Systems, 270-277. DOI: https://doi.org/10.1007/978-3-642-04592-9_34
Kwarteng, A. & Asante, B. (2017). Optimal Advertisement Placement Slot using Knapsack Problem. Int. Journal of Engineering Research and Application, 7(4), 46-62. DOI: https://doi.org/10.9790/9622-0704044662
Martello, S., & Monaci, M. (2020). Algorithmic approaches to the multiple knapsack assignment problem. Omega, (9), 102004. DOI: https://doi.org/10.1016/j.omega.2018.11.013
Yang, Y., Boland, N., & Savelsbergh, M. (2019). Multi-variable branching: A case study with 0-1 knapsack problems. Optimization Online. https://www.researchgate.net/profile/ Yu-Yang-149/publication/340964301_ Multi-Variable_Branching_A_Case_ Study_with_0-1_Knapsack_Problems/ links/5ea7a95b45851553fab5ead7/Multi- Variable-Branching-A-Case-Study-with-0- 1-Knapsack-Problems.pdf
