Since its appearance in 1947, the primal simplex algorithm has been one of the most popular algorithm for solving linear programs. It is very efficient when there is very little degeneracy, but it often struggles in the presence of high degeneracy, executing many pivots without improving the objective function value. In this paper, we propose an improved primal simplex algorithm that deals with this issue. This algorithm is based on new theoretical results that shed light on how to reduce the negative impact of degeneracy. In particular, we show that, from a degenerate basic solution with p positive-valued variables, a maximum of m-p+1 simplex pivots is needed to improve the objective value where m is the number of constraints in the linear program. Finally, we report computational results that show the effectiveness of the proposed algorithm on degenerate linear programs.
Published September 2007 , 24 pages