A Modified Bisection Simplex Method for Linear Programming (Journal of Computational Mathematics, 1996)
In this paper, a modification of the bisection simplex method$^{[7]}$ 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 $b_0$ of the optimal value and an estimate of the error bound of $b_0$ (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 of such sizes as those tested.