THE BRANCH AND BOUND APPROACH TO A BOUNDED KNAPSACK PROBLEM (CASE STUDY: OPTIMIZING OF PENCAK SILAT MATCH SESSIONS)
Abstract
A method commonly employed to solve integer programming problems is the Branch and Bound. In this article, maximizing the number of matches held on the first day of pencak silat tournaments is essential because it can impact the overall dynamics and results of the competition. The model used to maximize the number of match sessions in pencak silat competitions is a variant of the Bounded Knapsack Problem (BKP), belonging to the category of integer programming models. The result obtained using the Branch and Bound method ensures that the maximum number of match sessions can be conducted. The objective value obtained using the Branch and Bound method decreases as it descends, indicating a decreasing maximum value.
Downloads
References
P. C. Gilmore and R. E. Gomory, "The theory and computation of knapsack functions," Operations Research, vol. 14, no. 6, pp. 1045-1074, 1966.
U. Pferschy, J. Schauer and C. Thielen, "Approximating the product knapsack problem," Optimization Letters, vol. 15, no. 8, pp. 2529-2540, 2021.
M. Assi and R. A. Haraty, "A survey of the knapsack problem," in In 2018 International Arab Conference on Information Technology (ACIT), 2018.
J. Jooken, P. Leyman and P. De Causmaecker, " A new class of hard problem instances for the 0–1 knapsack problem," European Journal of Operational Research, vol. 301, no. 3, pp. 841-854, 2022.
J. Jooken, P. Leyman and P. De Causmaecker, "Features for the 0-1 knapsack problem based on inclusionwise maximal solutions," European Journal of Operational Research, vol. 311, no. 1, pp. 36-55, 2023.
V. Cacchiani, M. Iori, A. Locatelli and S. Martello, "Knapsack problems—An overview of recent advances. Part II: Multiple, multidimensional, and quadratic knapsack problems," Computers & Operations Research, p. 143, 2022.
D. Pisinger, "A minimal algorithm for the bounded knapsack problem," INFORMS Journal on Computing, vol. 12, no. 1, pp. 75-82., 2000.
Z. Li, Y. He, H. L. Y. Li and X. Guo, "A novel discrete grey wolf optimizer for solving the bounded knapsack problem," in In Computational Intelligence and Intelligent Systems: 10th International Symposium, ISICA 2018, Jiujiang, China,, 2019.
S. Martello and P. Toth, Knapsack problems: algorithms and computer implementations, John Wiley & Sons, Inc., 1990.
H. Becker and L. S. Buriol, "An empirical analysis of exact algorithms for the unbounded knapsack problem," European Journal of Operational Research, vol. 277, no. 1, pp. 84-99, 2019.
M. Jemmali, "An optimal solution for the budgets assignment problem.," RAIRO-Operations Research, vol. 55, no. 2, pp. 873-897., 2021.
T. Fukunaga, "Approximation algorithms for a generalization of the maximum budget allocation," Journal of the Operations Research Society of Japan, vol. 64, no. 1, pp. 31-44, 2021.
R. Piedra de la Cuadra, "Knapsack models applied to the solution of complex problems in transport planning," 2023.
K. T. Nguyen and H. M. Le, "An integrated approach for allocation and scheduling-location problems on graphs," Computational and Applied Mathematics, vol. 43, no. 3, p. 147, 2024.
R. Kumar and R. Kleinberg, "Non-monotonic resource utilization in the bandits with knapsacks problem," Advances in Neural Information Processing Systems, vol. 35, pp. 19248-19259, 2022.
B. Sun, A. Zeynali, T. Li, M. Hajiesmaili, A. Wierman and D. H. Tsang, "Competitive algorithms for the online multiple knapsack problem with application to electric vehicle charging.," Proceedings of the ACM on Measurement and Analysis of Computing Systems, vol. 4, no. 3, pp. 1-32, 2020.
V. K. Tchendji and Y. F. Yankam, "Dynamic resource allocations in virtual networks through a knapsack problem's dynamic programming solution," Revue Africaine de Recherche en Informatique et Mathématiques Appliquées,, vol. 31, 2020.
C. Hertrich and M. Skutella, "Provably good solutions to the knapsack problem via neural networks of bounded size," INFORMS journal on computing, vol. 35, no. 5, pp. 1079-1097, 2023.
L. Han, C. Hao, C. Wu and Z. Zhang, "Approximation algorithms for the lower-bounded knapsack median problem," In International Conference on Algorithmic Applications in Management., pp. 119-130, 2020 August.
N. Ferdosian, M. Othman, B. M. Ali and K. Y. Lun, "Greedy–knapsack algorithm for optimal downlink resource allocation in LTE networks," Wireless Networks, vol. 22, pp. 1427-1440, 2016.
M. Aïder, O. Gacem and M. Hifi, "Branch and solve strategies-based algorithm for the quadratic multiple knapsack problem," Journal of the Operational Research Society, vol. 73, no. 3, pp. 540-557, 2022.
S. Coniglio, F. Furini and P. San Segundo, "A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts," European Journal of Operational Research, vol. 289, no. 2, pp. 435-455, 2021.
S. Coniglio, F. Furini and P. San Segundo, "A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts.," European Journal of Operational Research, vol. 289, no. 2, pp. 435-455, 2021.
M. Masmoudi, Y. Adouani and B. Jarboui, "LP relaxation and dynamic programming enhancing VNS for the multiple knapsack problem with setup," International Transactions in Operational Research, vol. 31, no. 3, pp. 1890-1916, 2024.
M. Al-Rabeeah, E. Munapo, A. Al-Hasani, S. Kumar and A. Eberhard, "Computational enhancement in the application of the branch and bound method for linear integer programs and related models," International Journal of Mathematical, Engineering and Management Sciences, vol. 4, no. 5, pp. 1140-1153, 2019.
R. M. Kolpakov, "Optimal strategy for solving a special case of the knapsack problem by the branch and bound method," Moscow University Mathematics Bulletin, pp. 97-106, 2021.
M. Cho, "The knapsack problem and its applications to the cargo loading problem," Anal. Appl. Math, vol. 13, pp. 48-63, 2019.
W. L. Winston, Operations research: applications and algorithms, Cengage Learning, 2022.
D. R. Morrison, S. H. Jacobson, J. J. Sauppe and E. C. Sewell, "Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning," Discrete Optimization, vol. 19, pp. 79-102, 2016.
L. A. Wolsey, Integer programming, John Wiley & Sons., 2020.
E. S. Kriswanto, Pencak Silat, Yogyakarta: Pustaka Baru Press, 2015.
PERSILAT, Peraturan Pertndingan Pencak SIlat, Persilat, 2022.
Copyright (c) 2024 Aditya Ambarwati, Sobri Abusini, Vira Hari Krisnawati
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Authors who publish with this Journal agree to the following terms:
- Author retain copyright and grant the journal right of first publication with the work simultaneously licensed under a creative commons attribution license that allow others to share the work within an acknowledgement of the work’s authorship and initial publication of this journal.
- Authors are able to enter into separate, additional contractual arrangement for the non-exclusive distribution of the journal’s published version of the work (e.g. acknowledgement of its initial publication in this journal).
- Authors are permitted and encouraged to post their work online (e.g. in institutional repositories or on their websites) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published works.
1.gif)
