IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v12y1966i7p588-608.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Gerald L. Thompson & Fred M. Tonge & Stanley Zionts, 1966. "Techniques for Removing Nonbinding Constraints and Extraneous Variables from Linear Programming Problems," Management Science, INFORMS, vol. 12(7), pages 588-608, March.
    • Handle: RePEc:inm:ormnsc:v:12:y:1966:i:7:p:588-608
    DOI: 10.1287/mnsc.12.7.588
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.12.7.588
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.12.7.588?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Bernard M. S. van Praag & Nico L. van der Sar, 1988. "Household Cost Functions and Equivalence Scales," Journal of Human Resources, University of Wisconsin Press, vol. 23(2), pages 193-210.
    2. Telgen, J., 1977. "On R.W. Llewellyn'S Rules To Identify Redundant Constraints; A Detailed Critique And Some Generalizations," Econometric Institute Archives 272155, Erasmus University Rotterdam.
    3. Löber, Gerrit & Staat, Matthias, 2010. "Integrating categorical variables in Data Envelopment Analysis models: A simple solution technique," European Journal of Operational Research, Elsevier, vol. 202(3), pages 810-818, May.
    4. Saito, G. & Corley, H.W. & Rosenberger, Jay M. & Sung, Tai-Kuan & Noroziroshan, Alireza, 2015. "Constraint Optimal Selection Techniques (COSTs) for nonnegative linear programming problems," Applied Mathematics and Computation, Elsevier, vol. 251(C), pages 586-598.
    5. van der Hoek, Gerard & Telgen, Jan, 1976. "Projective Methods To Find A Feasible Solution To Systems Of Linear Constraints," Econometric Institute Archives 272134, Erasmus University Rotterdam.
    6. Telgen, Jan, 1977. "Redundant And Non-Binding Constraints In Linear Programming Problems," Econometric Institute Archives 272156, Erasmus University Rotterdam.
    7. James Folberth & Stephen Becker, 2020. "Safe Feature Elimination for Non-negativity Constrained Convex Optimization," Journal of Optimization Theory and Applications, Springer, vol. 184(3), pages 931-952, March.
    8. Drynan, Ross G., 1987. "A Generalised Concept of Dominance in Linear Programming Models," Review of Marketing and Agricultural Economics, Australian Agricultural and Resource Economics Society, vol. 55(02), pages 1-7, August.
    9. M.A. Goberna & V. Jornet & M. Molina, 2003. "Saturation in Linear Optimization," Journal of Optimization Theory and Applications, Springer, vol. 117(2), pages 327-348, May.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:12:y:1966:i:7:p:588-608. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.