Abstract
Suppose that the simplex method is applied to a linear programming problem havingm equality constraints andr unrestricted variables. We give a method of performing the steps of the simplex method which reduces the arithmetic operation count byrm at each iteration. This savings in operations is achieved, since the method does not update the rows of the basis inverse associated with the unrestricted variables. Similar computational savings are achieved when the method is applied to the updating of anLU-factorization of the basis matrix.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Best, M. J., andCaron, R. J.,A Method to Increase the Computational Efficiency of Certain Quadratic Programming Algorithms, Mathematical Programming, Vol. 25, pp. 354–358, 1983.
Dantzig, G. B.,Linear Programming and Extensions, Princeton University Press, Princeton, New Jersey, 1963.
Bisschop, J., andMeeraus, A.,Matrix Augmentation and Structure Preservation in Linearly Constrained Control Problems, Mathematical Programming, Vol. 18, pp. 7–15, 1980.
Sherman, J., andMorrison, W. J.,Adjustment of an Inverse Matrix Corresponding to Changes in the Elements of a Given Column or a Given Row of the Original Matrix, Annals of Mathematical Statistics, Vol. 20, p. 621, 1949.
Reid, J. K.,A Sparsity-Exploiting Variant of the Bartels-Golub Decomposition for Linear Programming, Harwell, Report No. CSS-20, 1975.
Author information
Authors and Affiliations
Additional information
Communicated by D. F. Shanno
This research was supported by the Natural Sciences and Engineering Research Council of Canada under Grant No. A8189 and by a postgraduate fellowship.
Rights and permissions
About this article
Cite this article
Best, M.J., Caron, R.J. The simplex method and unrestricted variables. J Optim Theory Appl 45, 33–39 (1985). https://doi.org/10.1007/BF00940811
Issue Date:
DOI: https://doi.org/10.1007/BF00940811