A New Perturbation Simplex Algorithm for Linear Programming (Journal of Computational Mathematics, 1999)
In this paper, we first propose a perturbation procedure for achieving dual feasibility, which starts with any basis without introducing artificial variables. This procedure and the dual simplex method are then incorporated into a general purpose algorithm; then, a modification of it using a perturbation technique is made in order to handle highly degenerate problems efficiently. Some interesting theoretical results are presented. Numerical results obtained are reported, which are very encouraging through still preliminary.
Keywords: Linear programming; Simplex method; Perturbation; Dual feasibility.