Techniques for Removing Nonbinding Constraints and Extraneous Variables from Linear Programming Problems

Abstract

In formulating linear programming problems, analysts tend to include constraints that are not binding at the optimal solution for fear of excluding necessary constraints. The inclusion of such constraints does not alter the optimum solutions, but may require many additional iterations to be taken, as well as increase the computational difficulties encountered. Most of the methods proposed to date for identification of redundant and non-binding constraints are not warranted in practice because of the excessive computations required to implement them. These methods are reviewed in the present paper, and some of them are extended. A number of additional methods are also considered. Two of these new methods are not only practical, but have proven to be powerful in solving a number of problems. These methods may be incorporated in a variant of the simplex method. After each simplex iteration is made, constraints and variables are tested and, when identified as non-binding, are eliminated. The procedure is continued, with the problem size dwindling as the algorithm progresses, until the optimum is reached. Then the values of the eliminated variables are computed by substitution into the eliminated constraints. Early evidence shows that a size reduction for small problems (having 25-30 constraints) of 50 percent is not unusual. It is hoped that the results on larger problems will be even more significant.