Ilan Adler, Richard Karp and Ron Shamir

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-83-157
December 1983

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1983/CSD-83-157.pdf

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.

BibTeX citation:

@techreport{Adler:CSD-83-157,
    Author = {Adler, Ilan and Karp, Richard and Shamir, Ron},
    Title = {A Family of Simplex Variants Solving An m x d Linear Program in Expected Number of Pivot Steps Depending on d Only},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1983},
    Month = {Dec},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1983/5950.html},
    Number = {UCB/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.}
}

EndNote citation:

%0 Report
%A Adler, Ilan
%A Karp, Richard
%A Shamir, Ron
%T A Family of Simplex Variants Solving An m x d Linear Program in Expected Number of Pivot Steps Depending on d Only
%I EECS Department, University of California, Berkeley
%D 1983
%@ UCB/CSD-83-157
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1983/5950.html
%F Adler:CSD-83-157