Skip to main content
SpringerLink
Log in

On pricing and backward transformation in linear programming

  • Published:
Mathematical Programming Submit manuscript

Abstract

In this paper we re-examine some of the available methods for pricing out the columns in the simplex method and point out their potential advantages and disadvantages. In particular, we show that a simple formula for updating the pricing vector can be used with some advantage in the standard product form simplex algorithm and with very considerable advantage in two recent developments: P.M.J. Harris' dynamic scaling method and the Forrest—Tomlin method for maintaining triangular factors of the basis.

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. E.M.L. Beale,Mathematical programming in practice (Pitmans, London, 1968).

    Google Scholar 

  2. J. de Buchet, “How to take into account the low density of matrices to design a mathematical programming package”, in:Large sparse sets of linear equations Ed. J.K. Reid (Academic Press, London, 1971) pp. 211–217.

    Google Scholar 

  3. G.B. Dantzig,Linear programming and extensions (Princeton University Press, Princeton, N.J., 1963).

    Google Scholar 

  4. J.J.H. Forrest and J.A. Tomlin, “Updating triangular factors of the basis to maintain sparsity in the product form simplex method”Mathematical Programming 2 (1972) 263–278.

    Google Scholar 

  5. P.M.J. Harris, “Pivot selection methods of the devex LP code”,Mathematical Programming 5 (1973) 1–28.

    Google Scholar 

  6. W. Orchard—Hays,Advanced linear programming computing techniques (McGraw—Hill, New York, 1968).

    Google Scholar 

  7. G. Zoutendijk,Methods of feasible directions (Elsevier, Amsterdam, 1960).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Stanford University, Stanford, California, USA

    J. A. Tomlin

Authors
  1. J. A. Tomlin
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Research and reproduction of this report was partially supported by the Office of Naval Research under contract N-00014-67-A-0112-0011; U.S. Atomic Energy Commission Contract AT(04-3)-326-PA #18; and National Science Foundation Grant GJ 30408X.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Tomlin, J.A. On pricing and backward transformation in linear programming. Mathematical Programming 6, 42–47 (1974). https://doi.org/10.1007/BF01580221

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Keywords

Search

Navigation