Solving NP-hard problem using a new relaxation of approximate methods
Keywords:
optimization problems, relaxation, approximate methods, penalty, augmented lagrangian methodsAbstract
A new approach has been introduced for solving NP-hardness problem in combinatorial optimization problems. Actully, our study focused on the relationship between the Lagrange method and Penalty method ,this paper introduce a new relaxation of the fesible region.Furthermore, NP hard problem has been tested and showed that the Augmented Lagrangian Approach outperformed the Penalty method. Finally, our study focuses on enhancing the theoretical convergence features as well as numerical computing.
Downloads
References
Al-Jilawi, Ahmed. Solving the Semidefinite Programming Relaxation of Max-cut Using an Augmented Lagrangian Method. Northern Illinois University, 2019.
Hochba, Dorit S., ed. "Approximation algorithms for NP-hard problems." ACM Sigact News 28.2 (1997): 40-52.
Ilango, R., Loff, B., & Oliveira, I. C. (2020). NP-hardness of circuit minimization for multi-output functions. In 35th Computational Complexity Conference (CCC 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik.
Yu Du and Andrzej Ruszczyński. Rate of convergence of the bundle method. Journal of Optimization Theory and Applications, 173(3):908–922, 2017.
Marko Mäkelä. Survey of bundle methods for nonsmooth optimization. Optimization methods and software, 17(1):1–29, 2002.
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.
Baltean-Lugojan, R., & Misener, R. (2018). Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to NP-hardness. Journal of Global Optimization, 71(4), 655-690.
Magdon-Ismail, M. (2017). NP-hardness and inapproximability of sparse PCA. Information Processing Letters, 126, 35-38.
Yu Du and Andrzej Ruszczyński. Rate of convergence of the bundle method. Journal of ptimization Theory and Applications, 173(3):908–922, 2017.
Didehvar, F. (2020). Fuzzy Time & NP Hardness (P*= BPP*, P*≠ NP*)..
Vassilevska Williams, Virginia. "Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk)." 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015.
Alridha, A., Salman, A. M., & Al-Jilawi, A. S. (2021, March). The Applications of NP-hardness optimizations problem. In Journal of Physics: Conference Series (Vol. 1818, No. 1, p. 012179). IOP Publishing.
Mlika, Z., Driouch, E., & Ajib, W. (2018). User association under SINR constraints in HetNets: Upper bound and NP-hardness. IEEE Communications Letters, 22(8), 1672-1675.
Mlika, Z., & Cherkaoui, S. (2020). Massive Access in Beyond 5G IoT Networks with NOMA: NP-hardness, Competitiveness and Learning. arXiv preprint arXiv:2002.07957.
Mann, Zoltán Ádám. "The top eight misconceptions about NP-hardness." Computer 50.5 (2017): 72-79.
Salman, A. M., Alridha, A., & Hussain, A. H. (2021, March). Some Topics on Convex Optimization. In Journal of Physics: Conference Series (Vol. 1818, No. 1, p. 012171). IOP Publishing.
Alridha, A., & Al-Jilawi, A. S. (2021, March). Mathematical Programming Computational for Solving NP-Hardness Problem. In Journal of Physics: Conference Series (Vol. 1818, No. 1, p. 012137). IOP Publishing.
Kadhim, M. K., Wahbi, F. A., & Hasan Alridha, A. (2022). Mathematical optimization modeling for estimating the incidence of clinical diseases. International Journal of Nonlinear Analysis and Applications, 13(1), 185-195.
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.
Shubham Sharma & Ahmed J. Obaid (2020) Mathematical modelling, analysis and design of fuzzy logic controller for the control of ventilation systems using MATLAB fuzzy logic toolbox, Journal of Interdisciplinary Mathematics, 23:4, 843-849, DOI: 10.1080/09720502.2020.1727611
Published
How to Cite
Issue
Section
Copyright (c) 2022 International journal of health sciences
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Articles published in the International Journal of Health Sciences (IJHS) are available under Creative Commons Attribution Non-Commercial No Derivatives Licence (CC BY-NC-ND 4.0). Authors retain copyright in their work and grant IJHS right of first publication under CC BY-NC-ND 4.0. Users have the right to read, download, copy, distribute, print, search, or link to the full texts of articles in this journal, and to use them for any other lawful purpose.
Articles published in IJHS can be copied, communicated and shared in their published form for non-commercial purposes provided full attribution is given to the author and the journal. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
This copyright notice applies to articles published in IJHS volumes 4 onwards. Please read about the copyright notices for previous volumes under Journal History.
