The primal-dual simplex algorithm base on the most obtuse angle principle

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 \u00a0We \u00a0present \u00a0a \u00a0relaxation \u00a0algorithm \u00a0for \u00a0solving \u00a0linear \u00a0programming \u00a0(LP) \u00a0problems \u00a0under \u00a0the 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 \u00a0traditional \u00a0two-stage \u00a0simplex \u00a0algorithm. \u00a0Iterations \u00a0for \u00a0sub-problems \u00a0take \u00a0up \u00a0a \u00a0significant \u00a0proportion, 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.