A generalization of the steepest-edge rule and its number of simplex iterations for a nondegenerate LP

Abstract

In this paper, we propose a $p$-norm rule, which is a generalization of the steepest-edge rule, as a pivoting rule for the simplex method. For a nondegenerate linear programming problem, we show upper bounds for the number of iterations of the simplex method with the steepest-edge and $p$-norm rules. One of the upper bounds is given by a function of the number of variables, that of constraints, and the minimum and maximum positive elements in all basic feasible solutions.

arXiv comment16 pages