A Most-Obtuse-Angle Relaxation Algorithm For Linear Programming

Professor Ping-Qi Pan gave the heuristic characterization of the optimal basis (the principle of the most obtuse angle) and put forward the concept of "pivoting index" (Pan, 1990). The pivoting indices can reflect the angles formed by the gradients of the constraints and those of the objective function,and they can be taken as the bases to decide the priority of the entrance of the variable.This paper omit part of the constraints firstly,so we can get a relaxation problem with smaller scale,we can use simplex method to solve it ,then add up the constraints omitted before to resume the primal problem; if all the constraints are met,then we get a basic optimal solution.Oterwise, we continue to solve it with dual simplex method to get the basic optimal solution.Our preliminary computational tests show,compared with the conventional phase two simplex method, the algorithm put forward in this paper can reduce the iterations very effectively. Because the iterations which are used to solve the relaxation problem take the most part among these iterations,the average CPU time needed in one iteration can be reduced greatly. For the programs with large scales,the new algorithm has the potential advantage,it is a very promising algorithm.