A projective simplex method for linear programming

AbstractLinear programming problems with quite square coefficient matrix form a wide range of problems that are not amenable to existing algorithms. The method proposed in this paper attacks such problems from the dual side, alternatively arranging computations of the simplex method using the QR factorization. In each iteration, its tableau version handles an (n−m)×(n+1) tableau rather than the (m+1)×(n+1) conventional tableau, where m and n are the numbers of rows and columns of the coefficient matrix. In contrast to the simplex method, where two m×m systems are solved per iteration, the new approach solves a single s×s(s⩽n−m) system only. It allows “nonbasis deficiency”, and hence could reduce computational work dramatically. A favorable complexity analysis is given for one of its implementations against its conventional counterpart. In addition, a new crash heuristic, having a clear geometrical meaning towards an optimal basis, is developed to provide “good” input. We also report numerical results obtained from our trials to give an insight into the method's behavior