Some Experimental Results of the Station Cone Algorithm Compared to the Simplex Algorithm for Linear Programming

In this paper we introduce a new variant of station cone algorithm to solve linear programming problems. It uses a series of interior points Ok to determine the entering variables. The number of these interior points is finite and they move toward the optimal point. At each step, the calculation of new vertex is a simplex pivot. The proposed algorithm will be a polynomial time algorithm if the number of points Ok is limited by a polynomial function. The second objective of this paper is to carry out experimental calculations and compare with simplex methods and dual simplex method. The results show that the number of pivots of the station cone algorithm is less than 30 to 50 times that of the dual algorithm. And with the number of variables n and the number of constraints m increasing, the number of pivots of the dual algorithm is growing much faster than the number of pivots of the station cone algorithm. This conclusion is drawn from the computational experiments with n?500 and m?2000. In particular we also test for cases where n = 2, m = 100 000 and n = 3, m = 200 000. For case where n = 2 and m = 100 000, station cone algorithm is given no more than 16 pivots. In case of n = 3, m = 200 000, station cone algorithm has 23 pivots. The test has confirmed the trend that as the number of variables and constraints increases, the number of pivots of the simplex algorithm increases more rapidly than the number of pivots of the station cone algorithm.