Most-Obtuse-Angle Criss-Cross Alogrithms For Linear Programming

Zionts' (1969) criss-cross algorithm for solving linear programming problems is a pivotal one without prerequisite for an initial feasible basis[28]. The algorithm performs primal and dual iterations alternately. After that, a finite criss-cross algorithm was independently proposed by Chang[l], Terlaky[24] and Wang[29] , which terminates in finitely many iterations. One advantage of the criss-cross algorithms is that there is no need for any Phase-1 procedure, and any basis will be equally fine to start with. Unfortunately, such kind of algorithms require too many iterations in general, and perform unsatisfactorily in practice.It is noticeable that Ping-Qi Pan's ratio-test-free pivot rules[13, 11, 14, 12] reduce the computational complexity per iteration, especially the most-obtuse-angle rule bears attractive geometric meanings and performs very favorably in practice[14, 20, 31]. Based on the most-obtuse-angle rule, this paper establishes new criss-cross algorithms using the LU decomposition to improve efficiency further. In computational tests with 25 standard test problems from NETLIB, a code base on a dense implementation of a proposed algorithm outperformed MINOS 5.51, one of the best implementations of the simplex algorithm at present, in terms of iteration counts. These preliminary but encouraging computational results are reported.