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

Gerald L. Thompson, Fred M. Tonge and Stanley Zionts
Additional contact information
Gerald L. Thompson: Carnegie Institute of Technology
Fred M. Tonge: University of California, Irvine
Stanley Zionts: Carnegie Institute of Technology and the U.S. Steel Applied Research Laboratory, Monroeville, Pennsylvania

Management Science, 1966, vol. 12, issue 7, 588-608

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.

Date: 1966
References: Add references at CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.12.7.588 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:12:y:1966:i:7:p:588-608

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().