Generalized Upper Bounds and Triangular Decomposition in the Simplex Method

摘要

Two recent advances in linear programming have been the very successful implementation of the Generalized Upper Bound (GUB) algorithm, due to Dantzig and Van Slyke and the new methods for updating triangular factors of the basis in the Simplex Method (Bartels, Forrest and Tomlin). The purpose of the note is to show that despite the special basis inverse manipulation involved in one step of the GUB algorithm these two techniques can be successfully combined. (Author)