A dual projective simplex method for linear programming

AbstractThe method proposed in this paper is a dual version of the projective simplex method, developed by the author. Providing a stable alternative setting for the dual simplex method, by handling a sequence of linear least squares problems using orthogonalization, the method is capable of handling a basis with columns fewer than rows of the coefficient matrix, and amenable to problems with n − m large relative to m, a wide range of problems with which the projective simplex method performs unsatisfactorily, in general. Based on a plausible characterization of an optimal solution, a dual crash heuristic is described to produce an initial “good” basis. Computational results obtained with a set of standard test problems from NETLIB are very encouraging