On Gradient Simplex Methods for Linear Programs

Abstract. A variety of pivot column selection rules based upon the gradient criteria (including the steepest edge) have been explored to improve the efficiency of the primal simplex method. Simplex-like algorithms have been proposed imbedding the gradient direction (GD) which includes all variables whose increase or decrease leads to an im-provement in the objective function. Recently a frame work has been developed in the simplex method to incorporate the reduced-gradient direction (RGD) consisting of only variables whose increase leads to an improvement in the objective function. In this pa-per, the results are extended to embed GD in the simplex method based on the concept of combining directions. Also mathematical properties related to combining directions as well as deleting a variable from all basic directions are presented