Skip to main content
SpringerLink
Log in

A degenerate extreme point strategy for the classification of linear constraints as redundant or necessary

  • Contributed Papers
  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

This paper presents a degenerate extreme point strategy for active set algorithms which classify linear constraints as either redundant or necessary. The strategy makes use of an efficient method for classifying constraints active at degenerate extreme points. Numerical results indicate that significant savings in the computational effort required to classify the constraints can be achieved.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Karwan, M. H., Lotfi, V., Telgen, J., andZionts, S., Editors,Redundancy in Mathematical Programming: A State of the Art Survey, Springer-Verlag, Berlin, Germany, 1983.

    Google Scholar 

  2. Boot, J. C. G.,On Trivial and Binding Constraints in Programming Problems, Management Science, Vol. 8, pp. 419–441, 1962.

    Google Scholar 

  3. Zionts, S.,Size Reduction Techniques of Linear Programming and Their Applications, Carnegie Institute of Technology, PhD Thesis, 1965.

  4. Thompson, G. L., Tonge, F. M., andZionts, S.,Techniques for Removing Nonbinding Constraints and Extraneous Variables from Linear Programming Problems, Management Science, Vol. 12, pp. 588–608, 1966.

    Google Scholar 

  5. Gal, T.,A Method for Determining Redundant Constraints, Redundancy in Mathematical Programming: A State of the Art Survey, Edited by M. H. Karwan, V. Lotfi, J. Telgen, and S. Zionts, Springer-Verlag, Berlin, Germany, pp. 36–52, 1983.

    Google Scholar 

  6. Telgen, J.,Identifying Redundancy in Systems of Linear Constraints, Redundancy in Mathematical Programming: A State of the Art Survey, Edited by M. H. Karwan, V. Lotfi, J. Telgen, and S. Zionts, Springer-Verlag, Berlin, Germany, pp. 53–59, 1983.

    Google Scholar 

  7. Rubin, D. S.,Finding Redundant Constraints in Sets of Linear Inequalities, Redundancy in Mathematical Programming: A State of the Art Survey, Edited by M. H. Karwan, V. Lotfi, J. Telgen, and S. Zionts, Springer-Verlag, Berlin, Germany, pp. 60–67, 1983.

    Google Scholar 

  8. Zionts, S., andWallenius, J.,A Method for Identifying Redundant Constraints and Extraneous Variables in Linear Programming, Redundancy in Mathematical Programming: A State of the Art Survey, Edited by M. H. Karwan, V. Lotfi, J. Telgen, and S. Zionts, Springer-Verlag, Berlin, Germany, pp. 28–35, 1983.

    Google Scholar 

  9. Dantzig, G. B.,Linear Programming and Extensions, Princeton University Press, Princeton, New Jersey, 1963.

    Google Scholar 

  10. Best, M. J., andRitter, K.,Linear Programminng: Active Set Analysis and Computer Programs, Prentice-Hall, Englewood Cliffs, New Jersey, 1985.

    Google Scholar 

  11. Caron, R. J., McDonald, J. F., andPonic, C. M.,Classification of Linear Constraints as Redundant or Necessary, University of Windsor, Windsor Mathematics Report No. WMR-85-09, 1985.

  12. Boneh, A.,Preduce: A Probabilistic Algorithm for Identifying Redundancy by a Random Feasible Point Generator, Redundancy in Mathematical Programming: A State of the Art Survey, Edited by M. H. Karwan, V. Lotfi, J. Telgen, and S. Zionts, Springer-Verlag, Berlin, Germany, pp. 108–134, 1983.

    Google Scholar 

  13. Mangasarian, O. L.,Nonlinear Programming, McGraw-Hill, New York, New York, 1969.

    Google Scholar 

  14. Bland, R. G.,New Finite Pivoting Rules for the Simplex Method, Mathematics of Operations Research, Vol. 2, pp. 103–107, 1977.

    Google Scholar 

  15. Caron, R. J., McDonald, J. F., andPonic, C. M., Clasfy:A Fortran IV Subroutine to Classify Linear Constraints—Users' Guide, University of Windsor, Windsor Mathematics Report No. WMR-85-08, 1985.

  16. Kotiah, T. C. T., andSteinberg, D. I.,Occurrences of Cycling and Other Phenomena in a Class of Linear Problems, Communications of the Association of Computing Machinery, Vol. 20, pp. 107–112, 1977.

    Google Scholar 

  17. Grierson, D. E., andAly, A. A.,Plastic Design under Combined Stresses, Journal of the Engineering Mechanics Division, ASCE, Vol. 106, pp. 585–607, 1980.

    Google Scholar 

  18. Keerthi, S. S., andGilbert, E. G.,Computation of Minimum Time Feedback Control Laws for Discrete-Time Systems with State-Control Constraints, Paper Presented at the Conference on Information Sciences and Systems, Princeton University, Princeton, New Jersey, 1986.

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics and Statistics, University of Windsor, Windsor, Canada

    R. J. Caron (Associate Professor), J. F. McDonald (Professor) & C. M. Ponic (Research Assistant)

Authors
  1. R. J. Caron
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J. F. McDonald
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. C. M. Ponic
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by D. F. Shanno

This research was supported by the Natural Sciences and Engineering Research Council of Canada under Grants A8807 and A4625 and by an Undergraduate Summer Research Award.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Caron, R.J., McDonald, J.F. & Ponic, C.M. A degenerate extreme point strategy for the classification of linear constraints as redundant or necessary. J Optim Theory Appl 62, 225–237 (1989). https://doi.org/10.1007/BF00941055

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00941055

Key Words

Search

Navigation