Solving NP-Hard Problem With The Semidefinite Programming Field
E. Mousa. CENTRAL ASIAN JOURNAL OF MATHEMATICAL THEORY AND COMPUTER SCIENCES, 4 (1):
21-28(January 2023)
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.
%0 Journal Article
%1 noauthororeditor
%A Mousa, Ekhlas Annon
%D 2023
%J CENTRAL ASIAN JOURNAL OF MATHEMATICAL THEORY AND COMPUTER SCIENCES
%K Independent Lagrangian Maximum NP Optimization Problem, Set Technique, and hard method method, problemspenalty programming semidefinite
%N 1
%P 21-28
%T Solving NP-Hard Problem With The Semidefinite Programming Field
%U https://cajmtcs.centralasianstudies.org/index.php/CAJMTCS/article/view/350/372
%V 4
%X 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.
@article{noauthororeditor,
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.},
added-at = {2023-09-02T12:00:38.000+0200},
author = {Mousa, Ekhlas Annon},
biburl = {https://www.bibsonomy.org/bibtex/220bcb6835802b29bde4ed881343f5a65/centralasian_20},
interhash = {a149fc1aa462db935dc09bcddbc94227},
intrahash = {20bcb6835802b29bde4ed881343f5a65},
issn = {2660-5309},
journal = {CENTRAL ASIAN JOURNAL OF MATHEMATICAL THEORY AND COMPUTER SCIENCES},
keywords = {Independent Lagrangian Maximum NP Optimization Problem, Set Technique, and hard method method, problemspenalty programming semidefinite},
language = {english},
month = jan,
number = 1,
pages = {21-28},
timestamp = {2023-09-04T10:40:40.000+0200},
title = {Solving NP-Hard Problem With The Semidefinite Programming Field},
url = {https://cajmtcs.centralasianstudies.org/index.php/CAJMTCS/article/view/350/372},
volume = 4,
year = 2023
}