A Block-LU Update for Large-Scale Linear Programming
The paper deals with the simplex method for the standard large sparse linear programming problem. Stable and efficient updates to the basis matrix factors are vital to the computational success. The updating technique of \textit{P. E. Gill}, \textit{W. Murray}, the second author and \textit{M. H. Wright} [SIAM J. Sci. Stat. Comput. 5, 562--589 (1984; Zbl 0559.65042)], based on the block-LU factors of an expanding basis is examined. The main conclusions are: a) the block-LU update technique is a viable alternative to the standard updating technique of Bartels and Golub [cf. \textit{R. H. Bartels}, Numer. Math. 16, 414--434 (1971; Zbl 0197.43305)] when vectorization is available, b) numerical experiments on a CRAY Y-MP show the block-LU update to be superior to Bartels-Golub updating on 27 of 30 large, sparse test problems, c) the block-LU update possesses the same stability properties as the update of Bartels and Golub.
- A fast LU update for linear programming
- Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II
- A reduced proximal-point homotopy method for large-scale non-convex BQP
- Novel update techniques for the revised simplex method
- Methods for convex and general quadratic programming
- An efficient basis update for asymptotic linear programming
- A structure-preserving pivotal method for affine variational inequalities
- Complementarity framework for non linear dynamic analysis of skeletal structures with softening plastic hinges
- scientific article; zbMATH DE number 3852785 (Why is no real title available?)
- scientific article; zbMATH DE number 3856811 (Why is no real title available?)
- scientific article; zbMATH DE number 3858836 (Why is no real title available?)
- An efficient simplex LU factorization update
- scientific article; zbMATH DE number 4059114 (Why is no real title available?)
- A factorization with update procedures for a KKT matrix arising in direct optimal control
- Computing Sparse LU Factorizations for Large-Scale Linear Programming Bases
- scientific article; zbMATH DE number 176402 (Why is no real title available?)
- scientific article; zbMATH DE number 1971712 (Why is no real title available?)
- Updating the Triangular Factorization of a Matrix
- A simplex method algorithm using a double basis
- The double pivot simplex method
- Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II
- Approximating polyhedra with sparse inequalities
- An efficient approach to updating simplex multipliers in the simplex algorithm
This page was built for publication: A Block-$LU$ Update for Large-Scale Linear Programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3988985)