A review of the LU update in the simplex algorithm

Autor:	Joseph M. Elble, Nikolaos V. Sahinidis
Rok vydání:	2012
Předmět:	Mathematical optimization Linear system General Decision Sciences Incomplete LU factorization Stone method LU decomposition law.invention Revised simplex method Matrix (mathematics) Simplex algorithm law Modeling and Simulation Transpose Algorithm Mathematics
Zdroj:	International Journal of Mathematics in Operational Research. 4:366
ISSN:	1757-5869 1757-5850
Popis:	In the simplex method for linear optimisation, two linear systems involving a square non-singular basis matrix B and its transpose are solved at each iteration. A column of B is then replaced, and the solution of these two linear systems is required again. For the past four decades, researchers have made considerable advancements in updating the sparse LU factors of the basis matrix in this algorithm. This paper reviews the state-of-the-art in LU update procedures, while analysing each procedure to gain a full understanding of the progress made in this area.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::2c79f78dc5c9a2e82237ca0ef654420d https://doi.org/10.1504/ijmor.2012.048901 Zobrazit plný text záznamu