IDEAS home Printed from https://ideas.repec.org/p/ags/eureia/272156.html
   My bibliography  Save this paper

Redundant And Non-Binding Constraints In Linear Programming Problems

Author

Listed:
  • Telgen, Jan

Abstract

General mathematical programming problems may contain redundant and nonbinding constraints. These are constraints, which can be removed from the problem without altering the feasible region or the optimal solution respectivily. Here we consider some more theoretical definitions and give reasons for selecting a special one. The emphasis is put on linear programming, but most of the material can be applied to any mathematical programming problem with linear constraints. To identify redundant constraints several methods have been proposed. We give a survey and show that all these methods are variants of a general method (Telgen (1977a)). No method is known to identify non-binding constraints directly; therefore we give some indirect ways to identify non-binding constraints. Finally, some remarks are made concerning the importance of the methods to identify redundant and nonbinding constraints in practical linear programming problems, both from a managerial and from a computational point of view.

Suggested Citation

  • Telgen, Jan, 1977. "Redundant And Non-Binding Constraints In Linear Programming Problems," Econometric Institute Archives 272156, Erasmus University Rotterdam.
    • Handle: RePEc:ags:eureia:272156
    DOI: 10.22004/ag.econ.272156
    as

    Download full text from publisher

    File URL: https://ageconsearch.umn.edu/record/272156/files/erasmus093.pdf
    Download Restriction: no
    File URL: https://ageconsearch.umn.edu/record/272156/files/erasmus093.pdf?subformat=pdfa
    Download Restriction: no
    File URL: https://libkey.io/10.22004/ag.econ.272156?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
    ---><---

    References listed on IDEAS

    as
    1. J. C. G. Boot, 1962. "On Trivial and Binding Constraints in Programming Problems," Management Science, INFORMS, vol. 8(4), pages 419-441, July.
    2. 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.
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. Telgen, Jan, 1977. "On Redundancy In Systems Of Linear Inequalities," Econometric Institute Archives 272154, Erasmus University Rotterdam.
    2. Nijkamp, P. & Spronk, J., 1978. "Interactive multiple goal programming," Serie Research Memoranda 0003, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. 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.
    2. 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.
    3. Miguel Goberna & Valentín Jornet & Mariola Molina, 2005. "Uniform saturation in linear inequality systems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 13(1), pages 167-184, June.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.

    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:ags:eureia:272156. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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: AgEcon Search (email available below). General contact details of provider: https://edirc.repec.org/data/feeurnl.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.