On the Simplex Method using an Artificial Basis

Kallio, M.J. (1979). On the Simplex Method using an Artificial Basis. IIASA Working Paper. IIASA, Laxenburg, Austria: WP-79-025

Preview

Text WP-79-025.pdf Download (395kB) | Preview

Abstract

The use of an artificial basis for the simplex method was suggested in an early paper by Dantzig. The idea is based on an observation that certain bases, which differ only in a relatively few columns from the true basis, may be easily inverted. Such artificial bases can then be exploited when carrying out simplex iterations. This idea was originally suggested for solving structured linear programming problems, and several approaches, such as Beale's method of pseudo-basic variables, have indeed been presented in the literature.

In this paper, we shall not consider the structure explicitly; rather its exploitation in our case is expected to result directly from the choice of an artificial basis. We shall consider this basis to remain unchanged over a number of simplex iterations. In particular, this basis may be chosen as the true basis which has been most recently reinverted. In such a case our approach yields an interpretation for a basis representation recently proposed by Bisschop and Meeraus who point out very favorable properties regarding the build-up of nonzero elements in the basis representation.

Our approach utilizes an auxiliary basis, which is small relative to the true basis, and whose dimension may change from one iteration to another. We shall finally develop an updating scheme for a product form representation of the inverse of such an auxiliary basis.

Actions (login required)

View Item