×

A practical anti-cycling procedure for linearly constrained optimization. (English) Zbl 0688.90038

An anti-cycling procedure in active-set methods for general linearly constrained problems, including the simplex method, is described in this paper. Two features of the procedure are crucial: controlled infeasibility of all variables (including nonbasic) and a “working” feasibility tolerance that increases slightly and consistently through an extended sequence of iterations. The additional computation per iteration is nominal, and “stalling” cannot occur with exact arithmetic. The paper reports the authors’ computational results and the method appears to be reliable.
Reviewer: X.-S.Zhang

MSC:

90C05 Linear programming
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming

Software:

DEVEX; GAMS; LSSOL; MINOS; LPKIT
PDFBibTeX XMLCite
Full Text: DOI

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). · Zbl 0223.90016
[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. · Zbl 0333.65029
[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. · Zbl 0384.90084 · doi:10.1007/BF01584344
[4] R.G. Bland, ”New finite pivoting rules for the simplex method,”Mathematics of Operations Research 2 (1977) 103–107. · Zbl 0408.90050 · doi:10.1287/moor.2.2.103
[5] A. Brooke, D. Kendrick and A. Meeraus,GAMS: A User’s Guide (The Scientific Press, Redwood City, CA, 1988).
[6] G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, NJ, 1963).
[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). · Zbl 0666.65043
[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. · Zbl 0064.39402
[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). · Zbl 0639.90072
[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). · Zbl 0474.65043
[12] R. Fletcher, ”Degeneracy in the presence of round-off errors,” Technical Report NA/89, Department of Mathematical Sciences, University of Dundee (Dundee, 1985).
[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.
[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. · Zbl 0301.90032 · doi:10.1093/imamat/14.2.159
[15] R. Fourer, ”A simplex algorithm for piecewise-linear programming I: derivation and proof,”Mathematical Programming 33 (1985) 204–233. · Zbl 0579.90084 · doi:10.1007/BF01582246
[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.
[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).
[19] P.E. Gill and W. Murray, ”Numerically stable methods for quadratic programming,”Mathematical Programming 14 (1978) 349–372. · Zbl 0374.90054 · doi:10.1007/BF01588976
[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).
[21] P.E. Gill, W. Murray and M.H. Wright,Practical Optimization (Academic Press, London and New York, 1981). · Zbl 0503.90062
[22] G.W. Graves, ”A complete constructive algorithm for the general mixed linear programming problem,”Naval Research Logistics Quarterly 12 (1965) 1–34. · Zbl 0171.17703 · doi:10.1002/nav.3800120102
[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.
[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.] · Zbl 0261.90031 · doi:10.1007/BF01580108
[25] E.S. Klotz,Dynamic pricing criteria in linear programming, Ph.D. thesis, Department of Operations Research, Stanford University (Stanford, CA, 1988).
[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.] · Zbl 0661.90056
[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).
[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).
[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. · Zbl 0613.90064 · doi:10.1145/22721.22959
[30] J.L. Nazareth,Computer Solution of Linear Programs (Oxford University Press, New York and Oxford, 1987). · Zbl 0643.90042
[31] W. Ogryczak, ”On practical stopping rules for the simplex method,”Mathematical Programming Study 31 (1987) 167–174. · Zbl 0636.90057
[32] W. Orchard-Hays,Advanced Linear-Programming Computing Techniques (McGraw-Hill, New York, 1968). · Zbl 0995.90595
[33] J.M. Ortega and W.C. Rheinboldt,Iterative Solution of Nonlinear Equations in Several Variables (Academic Press, London and New York, 1970). · Zbl 0241.65046
[34] M.R. Osborne,Finite Algorithms in Optimization and Data Analysis (Wiley, New York, 1985). · Zbl 0573.65044
[35] R.T. Rockafellar,Network Flows and Monotropic Optimization (Wiley, New York, 1984). · Zbl 0596.90055
[36] D.M. Ryan and M.R. Osborne, ”On the solution of highly degenerate linear programs,”Mathematical Programming 41 (1988) 385–392. · Zbl 0651.90045 · doi:10.1007/BF01580776
[37] J.H. Wilkinson,The Algebraic Eigenvalue Problem (The Clarendon Press, Oxford, 1965). · Zbl 0258.65037
[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. · Zbl 0127.36903 · doi:10.1137/0111016
[40] P. Wolfe, ”The composite simplex algorithm,”SIAM Review 7 (1965) 42–54. · Zbl 0133.42703 · doi:10.1137/1007004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.