The primal-dual simplex algorithm base on the most obtuse angle principle
Cited by
Export citation
- BibTex
- RIS
- TXT
@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}
}
TY - JOUR
T1 - The primal-dual simplex algorithm base on the most obtuse angle principle
AU - Wenya Gu, Xiangrui Meng, Xiaochen Zhu, Xinfa Qiu and Pingqi Pan
JO - Journal of Information and Computing Science
VL - 3
SP - 190
EP - 194
PY - 2024
DA - 2024/01
SN - 13
DO - http://doi.org/
UR - https://global-sci.org/intro/article_detail/jics/22444.html
KW - linear programming, primal-dual simplex algorithm, the most obtuse Angle
principle, sub-problem
AB - 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.
Wenya Gu, Xiangrui Meng, Xiaochen Zhu, Xinfa Qiu and Pingqi Pan. (2024). The primal-dual simplex algorithm base on the most obtuse angle principle.
Journal of Information and Computing Science. 13 (3).
190-194.
doi:
Copy to clipboard