Solving NP-Hard Problem With The Semidefinite Programming Field
Keywords:
Optimization Technique, Maximum Independent Set Problem, NP hard problems, penalty method and Lagrangian method, semidefinite programming
Abstract
In this paper we have study the solution to the Maximum Independent Set optimization problem in semidefinite programming field. In fact, a new approach has been developed to replace the penalty method with the augmented Lagrangian method according to the value of the parameter. Also, a combined method that switches between the two methods was developed called the combined method. The proposed three approaches of the augmented Lagrangian problem, and the penalty problem were studied for the linear programming (LP) problems. As a result, only two approaches were justified and approved as valid methods to be used for solving the SDP relaxations. Finally, Julia language was applied to obtain the numerical results.
References
1. Kizielewicz, B., & Sałabun, W. (2020). A new approach to identifying a multi-criteria decision model based on stochastic optimization techniques. Symmetry, 12(9), 1551.
2. Yang, X. S. (2020). Nature-inspired optimization algorithms. Academic Press.
3. Ahmadian, A., Mohammadi-Ivatloo, B., & Elkamel, A. (Eds.). (2020). Electric vehicles in energy systems: Modelling, integration, analysis, and optimization. Basilea: Springer.
4. Al-Jilawi, A. S., & Abd Alsharify, F. H. (2022). Review of Mathematical Modelling Techniques with Applications in Biosciences. Iraqi Journal For Computer Science and Mathematics, 3(1), 135-144.
5. Al-Jilawi, A. S., & Abd Alsharify, F. H. (2022). Review of Mathematical Modelling Techniques with Applications in Biosciences. Iraqi Journal For Computer Science and Mathematics, 3(1), 135-144.
6. ALRIDHA, A. H., Mousa, E. A., & Al-Jilawi, A. S. (2022). Review of Recent Uncertainty Strategies within Optimization Techniques. Central Asian Journal of Theoretical and Applied Science, 3(6), 160-170.
7. ALRIDHA, A. H., Salman, A. M., & Al-Jilawi, A. S. (2022). Numerical Optimization Approach for Solving Production Planning Problem Using Python language. CENTRAL ASIAN JOURNAL OF MATHEMATICAL THEORY AND COMPUTER SCIENCES, 3(6), 6-15.
8. Cook, W. (2019). Computing in combinatorial optimization. In Computing and Software Science (pp. 27-47). Springer, Cham.
9. Krislock, N., Malick, J., & Roupin, F. (2012). Improved semidefinite branch-and-bound algorithm for k-cluster. Available online as preprint hal-00717212.
10. Krislock, N., Malick, J., & Roupin, F. (2016). Computational results of a semidefinite branch-and-bound algorithm for k-cluster. Computers & Operations Research, 66, 153-159.
11. Strekalovsky, A., Kochetov, Y., Gruzdeva, T., & Orlov, A. (Eds.). (2021). Mathematical Optimization Theory and Operations Research: Recent Trends: 20th International Conference, MOTOR 2021, Irkutsk, Russia, July 5–10, 2021, Revised Selected Papers.
12. Alridha, A., Wahbi, F. A., & Kadhim, M. K. (2021). Training analysis of optimization models in machine learning. International Journal of Nonlinear Analysis and Applications, 12(2), 1453-1461.
13. Alridha, A. H., & Al-Jilawi, A. S. (2022). Solving NP-hard problem using a new relaxation of approximate methods. International Journal of Health Sciences, 6, 523-536.
14. Wiegele, A. (2007). Biq Mac Library—A collection of Max-Cut and quadratic 0-1 programming instances of medium size. Preprint, 51.
15. Borchers, B. (1999). CSDP, AC library for semidefinite programming. Optimization methods and Software, 11(1-4), 613-623.
2. Yang, X. S. (2020). Nature-inspired optimization algorithms. Academic Press.
3. Ahmadian, A., Mohammadi-Ivatloo, B., & Elkamel, A. (Eds.). (2020). Electric vehicles in energy systems: Modelling, integration, analysis, and optimization. Basilea: Springer.
4. Al-Jilawi, A. S., & Abd Alsharify, F. H. (2022). Review of Mathematical Modelling Techniques with Applications in Biosciences. Iraqi Journal For Computer Science and Mathematics, 3(1), 135-144.
5. Al-Jilawi, A. S., & Abd Alsharify, F. H. (2022). Review of Mathematical Modelling Techniques with Applications in Biosciences. Iraqi Journal For Computer Science and Mathematics, 3(1), 135-144.
6. ALRIDHA, A. H., Mousa, E. A., & Al-Jilawi, A. S. (2022). Review of Recent Uncertainty Strategies within Optimization Techniques. Central Asian Journal of Theoretical and Applied Science, 3(6), 160-170.
7. ALRIDHA, A. H., Salman, A. M., & Al-Jilawi, A. S. (2022). Numerical Optimization Approach for Solving Production Planning Problem Using Python language. CENTRAL ASIAN JOURNAL OF MATHEMATICAL THEORY AND COMPUTER SCIENCES, 3(6), 6-15.
8. Cook, W. (2019). Computing in combinatorial optimization. In Computing and Software Science (pp. 27-47). Springer, Cham.
9. Krislock, N., Malick, J., & Roupin, F. (2012). Improved semidefinite branch-and-bound algorithm for k-cluster. Available online as preprint hal-00717212.
10. Krislock, N., Malick, J., & Roupin, F. (2016). Computational results of a semidefinite branch-and-bound algorithm for k-cluster. Computers & Operations Research, 66, 153-159.
11. Strekalovsky, A., Kochetov, Y., Gruzdeva, T., & Orlov, A. (Eds.). (2021). Mathematical Optimization Theory and Operations Research: Recent Trends: 20th International Conference, MOTOR 2021, Irkutsk, Russia, July 5–10, 2021, Revised Selected Papers.
12. Alridha, A., Wahbi, F. A., & Kadhim, M. K. (2021). Training analysis of optimization models in machine learning. International Journal of Nonlinear Analysis and Applications, 12(2), 1453-1461.
13. Alridha, A. H., & Al-Jilawi, A. S. (2022). Solving NP-hard problem using a new relaxation of approximate methods. International Journal of Health Sciences, 6, 523-536.
14. Wiegele, A. (2007). Biq Mac Library—A collection of Max-Cut and quadratic 0-1 programming instances of medium size. Preprint, 51.
15. Borchers, B. (1999). CSDP, AC library for semidefinite programming. Optimization methods and Software, 11(1-4), 613-623.
Published
2023-01-09
How to Cite
Ekhlas Annon Mousa. (2023). Solving NP-Hard Problem With The Semidefinite Programming Field. CENTRAL ASIAN JOURNAL OF MATHEMATICAL THEORY AND COMPUTER SCIENCES, 4(1), 21-28. Retrieved from https://cajmtcs.centralasianstudies.org/index.php/CAJMTCS/article/view/350
Section
Articles
