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 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.