Skip to main content
SpringerLink
Log in

A practical anti-cycling procedure for linearly constrained optimization

  • Published:
Mathematical Programming Submit manuscript

Abstract

A procedure is described for preventing cycling in active-set methods for linearly constrained optimization, including the simplex method. The key ideas are a limited acceptance of infeasibilities in all variables, and maintenance of a “working” feasibility tolerance that increases over a long sequence of iterations. The additional work per iteration is nominal, and “stalling” cannot occur with exact arithmetic. The method appears to be reliable, based on computational results for the first 53 linear programming problems in theNetlib set.

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. M.L. Balinski and R.E. Gomory, “A mutual primal-dual simplex method,” in: R.L. Graves and P. Wolfe, eds.,Recent Advances in Mathematical Programming (McGraw-Hill, New York, 1963).

    Google Scholar 

  2. E.M.L. Beale, “Advanced algorithmic features for general mathematical programming systems,” in: J. Abadie, ed.,Integer and Nonlinear Programming (North-Holland, Amsterdam, 1970) pp. 119–137.

    Google Scholar 

  3. M. Benichou, J.M. Gauthier, G. Hentges and G. Ribière, “The efficient solution of large-scale linear programming problems—some algorithmic techniques and computational results,”Mathematical Programming 13 (1977) 280–322.

    Google Scholar 

  4. R.G. Bland, “New finite pivoting rules for the simplex method,”Mathematics of Operations Research 2 (1977) 103–107.

    Google Scholar 

  5. A. Brooke, D. Kendrick and A. Meeraus,GAMS: A User's Guide (The Scientific Press, Redwood City, CA, 1988).

    Google Scholar 

  6. G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, NJ, 1963).

    Google Scholar 

  7. G.B. Dantzig, “Making progress during a stall in the simplex algorithm,” Report SOL 88-5, Department of Operations Research, Stanford University (Stanford, CA, 1988).

    Google Scholar 

  8. G.B. Dantzig, A. Orden and P. Wolfe, “The generalized simplex method for minimizing a linear form under linear inequality constraints,”Pacific Journal of Mathematics 5 (1955) 183–195.

    Google Scholar 

  9. J.C. Falkner, “Bus crew scheduling and the set partitioning model,” Ph.D. thesis, Department of Theoretical and Applied Mechanics, University of Auckland (Auckland, New Zealand, 1988).

    Google Scholar 

  10. J.C. Falkner and D.M. Ryan, “Aspects of bus crew scheduling using a set partitioning model,” Fourth International Workshop on Computer-Aided Scheduling of Public Transport (Hamburg, 1987).

  11. R. Fletcher,Practical Methods of Optimization: Vol. 2: Constrained Optimization (Wiley, Chichester and New York, 1981).

    Google Scholar 

  12. R. Fletcher, “Degeneracy in the presence of round-off errors,” Technical Report NA/89, Department of Mathematical Sciences, University of Dundee (Dundee, 1985).

    Google Scholar 

  13. R. Fletcher, “Recent developments in linear and quadratic programming,” in: A. Iserles and M.J.D. Powell, eds.,The State of the Art in Numerical Analysis (Oxford University Press, Oxford and New York, 1987) pp. 213–243.

    Google Scholar 

  14. R. Fletcher and M.P. Jackson, “Minimization of a quadratic function of many variables subject only to upper and lower bounds,”Journal of the Institute of Mathematics and its Applications 14 (1974) 159–174.

    Google Scholar 

  15. R. Fourer, “A simplex algorithm for piecewise-linear programming I: derivation and proof,”Mathematical Programming 33 (1985) 204–233.

    Google Scholar 

  16. R. Fourer and D.M. Gay, private communication (1989).

  17. D.M. Gay, “Electronic mail distribution of linear programming test problems,”Mathematical Programming Society COAL Newsletter 13 (1985) 10–12.

    Google Scholar 

  18. P.E. Gill, S.J. Hammarling, W. Murray, M.A. Saunders and M.H. Wright, “User's Guide for LSSOL (Version 1.0): a Fortran package for constrained linear least-squares and convex quadratic programming,” Report SOL 86-1, Department of Operations Research, Stanford Univesity (Stanford, CA, 1986).

    Google Scholar 

  19. P.E. Gill and W. Murray, “Numerically stable methods for quadratic programming,”Mathematical Programming 14 (1978) 349–372.

    Google Scholar 

  20. P.E. Gill, W. Murray, M.A. Saunders and M.H. Wright, “User's Guide for SOL/QPSOL (revised),” Report SOL 84-6, Department of Operations Research, Stanford University (Stanford, CA, 1984).

    Google Scholar 

  21. P.E. Gill, W. Murray and M.H. Wright,Practical Optimization (Academic Press, London and New York, 1981).

    Google Scholar 

  22. G.W. Graves, “A complete constructive algorithm for the general mixed linear programming problem,”Naval Research Logistics Quarterly 12 (1965) 1–34.

    Google Scholar 

  23. H.J. Greenberg, “Pivot selection tactics,” in: H.J. Greenberg, ed.,Design and Implementation of Optimization Software (Sijthoff and Noordhoff, Alphen aan den Rijn, 1978) pp. 143–174.

    Google Scholar 

  24. P.M.J. Harris, “Pivot selection methods of the Devex LP code,”Mathematical Programming 5 (1973) 1–28. [Reprinted inMathematical Programming Study 4 (1975) 30-57.]

    Google Scholar 

  25. E.S. Klotz,Dynamic pricing criteria in linear programming, Ph.D. thesis, Department of Operations Research, Stanford University (Stanford, CA, 1988).

    Google Scholar 

  26. I.J. Lustig, “An analysis of an available set of linear programming test problems,” Report SOL 87-11, Department of Operations Research, Stanford University (Stanford, CA, 1987). [See alsoComputers and Operations Research 16 (1989) 173–184.]

    Google Scholar 

  27. B.A. Murtagh and M.A. Saunders, “MINOS 5.0 User's Guide,” Report SOL 83-20, Department of Operations Research, Stanford University (Stanford, CA, 1983).

    Google Scholar 

  28. B.A. Murtagh and M.A. Saunders, “MINOS 5.1 User's Guide,” Report SOL 83-20R, Department of Operations Research, Stanford University (Stanford, CA, 1987).

    Google Scholar 

  29. J.L. Nazareth, “Implementation aids for the optimization algorithms that solve sequences of linear programs,”ACM Transactions on Mathematical Software 12 (1986) 307–323.

    Google Scholar 

  30. J.L. Nazareth,Computer Solution of Linear Programs (Oxford University Press, New York and Oxford, 1987).

    Google Scholar 

  31. W. Ogryczak, “On practical stopping rules for the simplex method,”Mathematical Programming Study 31 (1987) 167–174.

    Google Scholar 

  32. W. Orchard-Hays,Advanced Linear-Programming Computing Techniques (McGraw-Hill, New York, 1968).

    Google Scholar 

  33. J.M. Ortega and W.C. Rheinboldt,Iterative Solution of Nonlinear Equations in Several Variables (Academic Press, London and New York, 1970).

    Google Scholar 

  34. M.R. Osborne,Finite Algorithms in Optimization and Data Analysis (Wiley, New York, 1985).

    Google Scholar 

  35. R.T. Rockafellar,Network Flows and Monotropic Optimization (Wiley, New York, 1984).

    Google Scholar 

  36. D.M. Ryan and M.R. Osborne, “On the solution of highly degenerate linear programs,”Mathematical Programming 41 (1988) 385–392.

    Google Scholar 

  37. J.H. Wilkinson,The Algebraic Eigenvalue Problem (The Clarendon Press, Oxford, 1965).

    Google Scholar 

  38. P. Wolfe, “The reduced-gradient method,” unpublished manuscript, the RAND Corporation (1962).

  39. P. Wolfe, “A technique for resolving degeneracy in linear programming,”SIAM Journal of Applied Mathematics 11 (1963) 205–211.

    Google Scholar 

  40. P. Wolfe, “The composite simplex algorithm,”SIAM Review 7 (1965) 42–54.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of California, 92093, San Diego, La Jolla, CA, USA

    Philip E. Gill

  2. Systems Optimization Laboratory, Department of Operations Research, Stanford University, 94305, Stanford, CA, USA

    Walter Murray & Michael A. Saunders

  3. AT&T Bell Laboratories, Murray Hill, 07974, NJ, USA

    Margaret H. Wright

Authors
  1. Philip E. Gill
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Walter Murray
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Michael A. Saunders
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Margaret H. Wright
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

The material contained in this report is based upon research supported by the Air Force Office of Scientific Research Grant 87-01962; the U.S. Department of Energy Grant DE-FG03-87ER25030; National Science Foundation Grants CCR-8413211 and ECS-8715153; and the Office of Naval Research Contract N00014-87-K-0142.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gill, P.E., Murray, W., Saunders, M.A. et al. A practical anti-cycling procedure for linearly constrained optimization. Mathematical Programming 45, 437–474 (1989). https://doi.org/10.1007/BF01589114

Download citation

  • Issue Date:

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

Key words

Search

Navigation