Abstract
Many implementations of the simplex method require the row of the inverse of the basis matrixB corresponding to the pivot row at each iteration for updating either a pricing vector or the nonbasic reduced costs. In this note we show that if the Bartels—Golub algorithm [1, 2] or one of its variants is used to update theLU factorization ofB, then less computing is needed if one works with the factors of the updatedB than with those ofB. These results are discussed as they apply to the column selection algorithms recently proposed by Goldfarb and Reid [4, 5] and Harris [6].
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R.H. Bartels, “A stabilization of the simplex method”,Numerische Mathematik 16 (1971) 414–434.
R.H. Bartels and G.H. Golub, “The Simplex method for linear programming using LU decomposition”,Communications of the ACM 12 (1969) 266–268.
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.
D. Goldfarb and J.K. Reid, “A practicable steepest edge Simplex Algorithm”, Mathematical Programming 12 (1977) 361–371.
D. Goldfarb, “Using the steepest edge simplex algorithm to solve sparse linear programs”, in: J. Bunch and D. Rose, eds.,Sparse matrix computations. (Academic Press, New York, 1976) pp. 227–240.
P.M.J. Harris, “Pivoting selection methods of the Devex LP code”,Mathematical Programming 5 (1973) 1–28.
J.K. Reid, “A sparsity-exploiting variant of the Bartels—Golub decomposition for linear programming bases”, Harwell Rept. CCS 20, AERE Harwell (August 1975).
M.A. Saunders, “The complexity of LU updating in the Simplex method”, in: R.S. Anderssen and R.P. Brent, eds.,The complexity of computational problem solving (Queensland University Press, Queensland, 1976) pp. 214–230.
J.A. Tomlin, “On pricing and backward transformation in linear programming”,Mathematical Programming 6 (1974) 42–47.
P. Wolfe, “The composite simplex algorithm”,SIAM Review 7 (1965) 42–54.
Author information
Authors and Affiliations
Additional information
This research was supported in part by the National Science Foundation under Grant GJ 36472.
Rights and permissions
About this article
Cite this article
Goldfarb, D. On the Bartels—Golub decomposition for linear programming bases. Mathematical Programming 13, 272–279 (1977). https://doi.org/10.1007/BF01584343
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01584343