A modified bisection simplex method for linear programming

In this paper, a modification of the bisection simplex method is made for more general purpose use. Organized in an alternative simpler form, the modified version exploits information of the optimal value, as does the original bisection method, but no bracket on the optimal value is needed as part of input; instead, it only requires provision of an estimate b0 of the optimal value and an estimate of the error bound of b0 (it is not sensitive to these values though). Moreover, a new, ratio-test-free pivoting rule is proposed, significantly reducing computational cost at each iteration. Our numerical experiments show that the method is very promising, at least for solving linear programming problems such as those tested.