Simplex pivot rule emphasizing increment of nonbasic variables

Abstract

The simplex algorithm, first presented by George B. Dantzig, is a widely used method for solving a linear programming (LP) problem. One of the important steps of the simplex algorithm is applying a pivot rule, the rule to select an entering variable. An effective pivot rule can lead to an optimal solution of an LP problem with a small number of iterations but not necessarily small computational time if each iteration spends a lot of time. In a minimization problem, Dantzig’s pivot rule selects an entering variable corresponding to the most negative reduced cost. The concept is to have the maximum improvement in the objective value per unit change of an entering variable. However, in some problems, Dantzig’s rule may visit a large number of extreme points before reaching the optimal solution. In this thesis, we propose a pivot rule, called the absolute change pivot rule, that could reduce the number of such iterations over the Dantzig’s pivot rule. The idea is to have the maximum improvement in the value of an objective function by trying to block a leaving variable that makes a little change in the objective value as much as possible. This absolute change pivot rule is tested and compared the efficacy with Dantzig’s original pivot rule and other pivot rules.