Projective Pivoting Indices Based Simplex Algorithms

Among finite or anti-cycling pivoting rules, Bland's rule is noticeable for its remarkable simplicity [10]. However, it depends on the indices of the variables entirely, and its performance is unsatisfactory. To overcome this shortcoming, in [28] professor P.-Q. Pan presented the plausible characterization of an optimal solution, and gave a new pivoting rule based on so-called "pivoting indices" for solving LP problems with inequality constrains. In [35], the author defined the dual-pivoting indices for standard LP problems. We find that it does not characterize an optimal solution very satisfactorily. In this thesis, we introduce a new pivoting index system, called projective pivoting indices, using the orthogonal projection of the gradient of the objective function onto the null space of the constraint matrix, and show its promise of success in comparison to existing finite rules, practically.