A projective simplex algorithm using LU decomposition

AbstractRecently, we proposed a so-called “projective simplex method”, which is amenable to linear programming problems with quite square coefficient matrix. Since it is based on QR decomposition, however, the method is not a suitable choice for large and sparse problems unless n − m is far less than m, where m and n are the numbers of rows and columns of the coefficient matrix, respectively. To dodge this flaw, in this paper we propose a method using LU decomposition. In contrast to the simplex method, in which an (m + 1) × (n + 1) tableau is used, its tableau version handles an (n − m) × (n + 1) tableau. In each iteration, its revised version solves a single (n − m) × (n − m) system only, compared with the two m × m systems solved in the revised simplex method. A complexity analysis establishes its superiority over an implementation of the simplex method in the case of the coefficient matrix being not too flat. Of particular interest might be the introduction of deficient nonbasis via exploiting dual degeneracy to reduce computational work further. An LU decomposition-based crash heuristic is furnished to provide “good” input. Computational results are also reported to give an insight into its interesting and distinctive behavior