Computational Simulation and Algorithm Analysis for Solving Combinatorial Optimization Problems in Graph Theory and Discrete Mathematics
DOI:
https://doi.org/10.62951/ijamc.v1i3.273Keywords:
Computational Efficiency, Finite Difference Method, Iterative Methods, Partial Differential Equations, Solver OptimizationAbstract
Combinatorial optimization is a fundamental area in operations research and computer science, focusing on identifying optimal solutions from a finite set of possibilities. This study explores the integration of branch and bound methods with heuristic algorithms to address optimization problems in graph theory and discrete mathematics. Python was employed for algorithm implementation due to its flexibility and comprehensive computational libraries, enabling efficient data analysis and visualization. Several benchmark problems were examined, including the Traveling Salesman Problem (TSP), Minimum Spanning Tree (MST), and Graph Coloring. Simulations were conducted using datasets of varying sizes (small, medium, and large) to evaluate performance across different scales. The results demonstrate that the hybrid approach achieves a balance between solution quality and computational efficiency, outperforming brute-force methods in terms of speed while maintaining near-optimal accuracy. Tabulated results and graphical comparisons highlight the reduction in computation time and improved scalability of the proposed method. The findings suggest that combining systematic search strategies with heuristics offers a practical and effective framework for solving complex combinatorial optimization problems. Recommendations for future research include testing scalability with larger datasets, incorporating advanced metaheuristics, and applying the approach to real-world domains such as logistics and network design.
References
Almarzooq, S., & Albishi, N. (2021). Mathematical modelling for transportation with application to airline transportation network. In Handbook of Research on Decision Sciences and Applications in the Transportation Sector (pp. 28–51). IGI Global. https://doi.org/10.4018/978-1-7998-8040-0.ch002
Arkat, J., Abdollahzadeh, H., & Ghahve, H. (2012). A new branch and bound algorithm for cell formation problem. Applied Mathematical Modelling, 36(10), 5091–5100. https://doi.org/10.1016/j.apm.2011.12.047
Asani, E. O., Ayebga, P. O., Ayoola, J. A., Okeyinka, A. E., & Adebiyi, A. A. (2019). A preliminary study on the complexity of some heuristics for solving combinatorial optimization problems. International Journal of Engineering Research and Technology, 12(10), 1615–1620.
Ast, J., Wasseghi, R., & Nyhuis, P. (2021). A comparison of methods for determining performance based employee deployment in production systems. Production Engineering, 15(3–4), 335–342. https://doi.org/10.1007/s11740-021-01019-5
Bao, L. N. L., Le, D. H., & Nguyen, D. A. (2018). Application of combinatorial optimization in logistics. In Proceedings of the 2018 4th International Conference on Green Technology and Sustainable Development (GTSD) (pp. 329–334). IEEE. https://doi.org/10.1109/GTSD.2018.8595447
Bauß, J., Parragh, S. N., & Stiglmayr, M. (2024). On improvements of multi-objective branch and bound. EURO Journal on Computational Optimization, 12, 100099. https://doi.org/10.1016/j.ejco.2024.100099
Cappart, Q., et al. (2021). Combinatorial optimization and reasoning with graph neural networks. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI) (pp. 4348–4355). https://doi.org/10.24963/ijcai.2021/595
Cappart, Q., et al. (2023). Combinatorial optimization and reasoning with graph neural networks. Journal of Machine Learning Research, 24.
Cerqueus, A., Gandibleux, X., Przybylski, A., & Saubion, F. (2017). On branching heuristics for the bi-objective 0/1 unidimensional knapsack problem. Journal of Heuristics, 23(5), 285–319. https://doi.org/10.1007/s10732-017-9346-9
Cheng, S., Ting, T. O., & Yang, X.-S. (2014). Large-scale global optimization via swarm intelligence. In Springer Proceedings in Mathematics & Statistics, 97 (pp. 241–253). Springer. https://doi.org/10.1007/978-3-319-08985-0_10
Dawood, H. A. (2014). Graph theory and cyber security. In Proceedings of the 3rd International Conference on Advanced Computer Science Applications and Technologies (ACSAT 2014) (pp. 90–96). IEEE. https://doi.org/10.1109/ACSAT.2014.23
Ezugwu, A. E., Pillay, V., Hirasen, D., Sivanarain, K., & Govender, M. (2019). A comparative study of meta-heuristic optimization algorithms for 0-1 knapsack problem: Some initial results. IEEE Access, 7, 43979–44001. https://doi.org/10.1109/ACCESS.2019.2908489
Hvorecky, J., Korenova, L., & Barot, T. (2022). Combining brute force and IT to solve difficult problems. In Proceedings of the Asian Technology Conference in Mathematics (pp. 302–312).
Iskandar, A. F., Sani, A. F., Riyadi, R., Febriani, S., & Syambas, N. R. (2021). Fast heuristic algorithm optimization for travelling salesman problem. In Proceedings of the 2021 7th International Conference on Wireless Telematics (ICWT). IEEE. https://doi.org/10.1109/ICWT52862.2021.9678454
Joshi, J. (2021). Python, a reliable programming language for chemoinformatics and bioinformatics. In Chemoinformatics and Bioinformatics in the Pharmaceutical Sciences (pp. 279–304). Elsevier. https://doi.org/10.1016/B978-0-12-821748-1.00013-0
Kaveh, A., Rahami, H., & Shojaei, I. (2020). Definitions from graph theory and graph products. In Studies in Systems, Decision and Control, 290 (pp. 1–10). Springer. https://doi.org/10.1007/978-3-030-45549-1_1
Li, L., He, C., Cheng, R., & Pan, L. (2021). Large-scale multiobjective optimization via problem decomposition and reformulation. In Proceedings of the 2021 IEEE Congress on Evolutionary Computation (CEC) (pp. 2149–2155). IEEE. https://doi.org/10.1109/CEC45853.2021.9504820
Liu, Z. (2010). Single machine scheduling to minimize maximum lateness subject to release dates and precedence constraints. Computers & Operations Research, 37(9), 1537–1543. https://doi.org/10.1016/j.cor.2009.11.008
Myers, C. K., & Sethna, J. P. (2007). Python for education: Computational methods for nonlinear systems. Computing in Science & Engineering, 9(3), 75–79. https://doi.org/10.1109/MCSE.2007.56
Nakariyakul, S. (2014). A comparative study of suboptimal branch and bound algorithms. Information Sciences, 278, 545–554. https://doi.org/10.1016/j.ins.2014.03.072
Pardalos, P. M., Žilinskas, A., & Žilinskas, J. (2017). Multi-objective branch and bound. In Springer Optimization and Its Applications, 123 (pp. 45–56). Springer. https://doi.org/10.1007/978-3-319-61007-8_5
Przybylski, A., & Gandibleux, X. (2017). Multi-objective branch and bound. European Journal of Operational Research, 260(3), 856–872. https://doi.org/10.1016/j.ejor.2017.01.032
Rani, A., Bakshi, S., & Bansal, R. (2024). AI strategies for complex math problems: Optimization. In Proceedings of the 2nd IEEE International Conference on IoT, Communication and Automation Technology (ICICAT) (pp. 797–801). IEEE. https://doi.org/10.1109/ICICAT62666.2024.10923294
Rihane, K., Dabah, A., & Aitzai, A. (2022). Learning-based selection process for branch and bound algorithms. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC). IEEE. https://doi.org/10.1109/CEC55065.2022.9870384
Ryzhkov, F. V., Ryzhkova, Y. E., & Elinson, M. N. (2025). Python tools for structural tasks in chemistry. Molecular Diversity, 29(4), 3733–3752. https://doi.org/10.1007/s11030-024-10889-7
Singh, G., & Rizwanullah, M. (2022). Combinatorial optimization of supply chain networks: A retrospective & literature review. Materials Today: Proceedings, 62, 1636–1642. https://doi.org/10.1016/j.matpr.2022.04.366
Singhtaun, C., & Natsupakpong, S. (2017). A comparison of parallel branch and bound algorithms for location-transportation problems in humanitarian relief. International Journal of GEOMATE, 12(33), 38–44. https://doi.org/10.21660/2017.33.2563
Somefun, T. E., Owolabi, T., & Longe, O. M. (2025). Practical trade-offs in neural network optimization: Brute force search and gradient descent. Engineering Research Express, 7(2), 025203. https://doi.org/10.1088/2631-8695/adc5de
Su, L.-H., & Chen, C.-J. (2008). Minimizing total tardiness on a single machine with unequal release dates. European Journal of Operational Research, 186(2), 496–503. https://doi.org/10.1016/j.ejor.2006.07.051
Szydłowska-Samsel, J. (2024). Supporting algorithmic trading with machine learning: Progress in backend technology. In Lecture Notes in Networks and Systems, 1079 (pp. 131–141). Springer. https://doi.org/10.1007/978-3-031-66761-9_12
Vervust, W., Zhang, D. T., Ghysels, A., Roet, S., van Erp, T. S., & Riccardi, E. (2024). PyRETIS 3: Conquering rare and slow events without boundaries. Journal of Computational Chemistry, 45(15), 1224–1234. https://doi.org/10.1002/jcc.27319
Wang, R., & Guo, N. (2014). Dynamic vehicle scheduling with time windows model and optimization. Applied Mechanics and Materials, 539, 855–859. https://doi.org/10.4028/www.scientific.net/AMM.539.855
Wu, K., Gao, J., Chen, R., & Cui, X. (2019). Vertex selection heuristics in branch-and-bound algorithms for the maximum k-plex problem. International Journal on Artificial Intelligence Tools, 28(5), 1950015. https://doi.org/10.1142/S0218213019500155
Yu, K., Yang, Z., Liang, J., Qiao, K., Qu, B., & Suganthan, P. N. (2025). An individual adaptive evolution and regional collaboration based evolutionary algorithm for large-scale constrained multiobjective optimization problems. Swarm and Evolutionary Computation, 95, 101925. https://doi.org/10.1016/j.swevo.2025.101925
Yu’E, L. (2020). Discussion on propositional logic incorporating set thought into discrete mathematics. Journal of Physics: Conference Series, 1634(1), 012087. https://doi.org/10.1088/1742-6596/1634/1/012087
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 International Journal of Applied Mathematics and Computing
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
