A computational approach to pivot selection in the LP relaxation of set problems

It has long been known to the researchers that choosing a variable having the most negative reduced cost as the entering variable is not the best choice in the simplex method as shown by Harris (1975). Thus, suitable modifications in the pivot selection criteria may enhance the algorithm. Previous efforts such as that by Dantzig and steepest-edge rules for pivot selection are based on finding a unified strategy for entering variable in all linear programming problems. In the present work, a number of strategies for pivot selection in the LP relaxation of the set problems are proposed which consider the specific knowledge of the problem. A significant reduction in the number of iterations is achieved for a set of randomly generated test problems.