@Article{JICS-13-190,
author = {Wenya Gu, Xiangrui Meng, Xiaochen Zhu, Xinfa Qiu and Pingqi Pan},
title = {The primal-dual simplex algorithm base on the most obtuse angle principle},
journal = {Journal of Information and Computing Science},
year = {2024},
volume = {13},
number = {3},
pages = {190--194},
abstract = {1School of Binjiang, Nanjing University of Information Science & Technology, Nanjing 210044, China 
2School of Applied Meteorology, Nanjing University of Information Science & Technology, Nanjing 210044, China 
3Department of Mathematics, Southeast University, Nanjing 210000, China 
(Received March 12 2018, accepted August 28 2018) 
Abstract  We  present  a  relaxation  algorithm  for  solving  linear  programming  (LP)  problems  under  the 
framework of the primal-dual simplex algorithm. Each iteration, based on a heuristic representation of the 
optimal basis (the principle of the most obtuse Angle), the algorithm constructs and solves a sub-problem, 
whose objective function is the same as the original problem, but only contains partial constraints.The primal-
dual simplex algorithm is used to solve the sub-problem. If the sub-problem has an optimal solution or the 
sub-problem has no feasible solution, the constraint is added according to the principle of the obtuse Angle 
and then the final solution of the old sub-problem is taken as the starting point. Our preliminary numerical 
experiments show that the proposed algorithm can effectively reduce the number of iterations compared with 
the  traditional  two-stage  simplex  algorithm.  Iterations  for  sub-problems  take  up  a  significant  proportion, 
which greatly reduces the CPU time required for each iteration. The new algorithm has potential advantages 
in solving large-scale problems. It's a very promising new algorithm. 
},
issn = {1746-7659},
doi = {https://doi.org/},
url = {http://global-sci.org/intro/article_detail/jics/22444.html}
}