A non-basic variable based approach to solve LPs

In this document a modification of the tableau-based simplex method is presented to solve linear programs. This approach is at the midpoint between the tableau-based simplex method and the matrix simplex method. This algorithm uses a reduced setting for each iteration reducing the number of operations by using only the columns of non-basic variables and an auxiliary column. As a result, the partial pivoting process on non-basic columns and the auxiliary column uses less time compared to the other versions of the simplex. The gain in using this modification compared with the tableau-based and the matrix-based methods is twofold: First, compared with the tableau-based method, this version builds a smaller tableau, second, compared with the matrix-based method, no inverse or factorizations are required, only the partial pivot operation is needed. These two aspects lead to a reduction of operations and thereof a speed up of the process is achieved.