Skip to main content
SpringerLink
Log in

Eliminating columns in the simplex method for linear programming

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

Abstract

We propose a column-eliminating technique for the simplex method of linear programming. A pricing criterion is developed for checking whether a dual hyperplane corresponding to a column intersects a simplex containing all of the optimal dual feasible solutions. If the dual hyperplane has no intersection with this simplex, we can eliminate the corresponding column from further computation during the course of the simplex method.

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. Khachiyan, L. G.,A Polynomial Algorithm for Linear Programming, Soviet Mathematics Doklady, Vol. 20, pp. 191–194, 1979.

    Google Scholar 

  2. Karmarkar, N.,A New Polynomial-Time Algorithm for Linear Programming, Combinatorica, Vol. 4, pp. 373–395, 1984.

    Google Scholar 

  3. Todd, M. J.,Improved Bounds and Containing Ellipsoids in Karmarkar's Linear Programming Algorithm, Mathematics of Operations Research, Vol. 13, pp. 650–659, 1988.

    Google Scholar 

  4. Ye, Y.,Karmarkar's Algorithm and the Ellipsoid Method, Operations Research Letters, Vol. 4, pp. 177–182, 1987.

    Google Scholar 

  5. Ye, Y.,A “Build-Down” Scheme for Linear Programming, Mathematical Programming (to appear).

  6. Goldfarb, D., andHao, J., Private Communication, 1987.

  7. Cheng, M. C.,New Criteria for the Simplex Algorithm, Mathematical Programming, Vol. 19, pp. 230–236, 1980.

    Google Scholar 

  8. Cheng, M. C.,Generalized Theorems for Permanent Basic and Nonbasic Variables, Mathematical Programming, Vol. 31, pp. 229–234, 1985.

    Google Scholar 

  9. Telgen, J.,Identifying Redundant Constraints and Implicit Equalities in System of Linear Constraints, Management Science, Vol. 10, pp. 1209–1222, 1983.

    Google Scholar 

  10. Dantzig, G. B.,Linear Programming and Extensions, Princeton University Press, Princeton, New Jersey, 1983.

    Google Scholar 

  11. Dantzig, G. B., Private Communication, 1987.

Download references

Author information

Authors and Affiliations

  1. Department of Management Sciences, College of Business Administration, University of Iowa, Iowa City, Iowa

    Y. Ye (Visiting Assistant Professor)

Authors
  1. Y. Ye
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by R. A. Tapia

The author is grateful for many discussions with Professor G. B. Dantzig, Stanford University, and for his valuable suggestions about this work. The author also gratefully acknowledges the editor and two referees for their very helpful comments, corrections, and remarks.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ye, Y. Eliminating columns in the simplex method for linear programming. J Optim Theory Appl 63, 69–77 (1989). https://doi.org/10.1007/BF00940732

Download citation

  • Issue Date:

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

Key Words

Search

Navigation