A Family of Simplex Variants Solving An m x d Linear Program in Expected Number of Pivot Steps Depending on d Only
Technical Report Identifier: CSD-83-157
Abstract: We present a family of variants of the Simplex method, which are based on a Constraint-By-Constraint procedure: the solution to a linear program is obtained by solving a sequence of subproblems with an increasing number of constraints. We discuss several probabilistic models for generating linear programs. In all of them the underlying distribution is assumed to be invariant under changing the signs of rows or columns in the problem data. a weak regularity condition is also assumed. Under these models, for linear programs with d variables and m+d inequality constraints, the expected number of pivots required by these algorithms is bounded by a constant when the number of constraints tends to infinity. Since Smale's original model [S1] satisfies our probabilistic assumptions, the same results apply to his model. We also present some results for models generating only feasible linear programs, and for Bland's pivoting rule. We conclude with a discussion of our probabilistic models, and show why they are inadequate for obtaining meaningful results unless d and m are of the same order of magnitude.