The simplex method. A probabilistic analysis (Q1083366)

This is the book that researchers interested in the average analysis of the computational complexity of pivotal methods for linear programming have been waiting for. The author received the prestigious Lancaster award (1982) of the OR society of America for his pioneering work in this area, and announced his intention of writing the book at that time. Many variants of the simplex method for linear programming have been shown to exhibit exponential growth in computational requirements on classes of instances specially constructed by mathematicians to bring out their worst behavior. However, the simplex method and other variants of it, turned out to be extremely efficient mathematical tools for solving real world linear programming problems in extensive use by numerous practitioners all over the world over the last 40 years. This tremendous discrepancy between the bad worst case behavior, and the good behavior on real world problems has always fascinated mathematicians. The lure of average analysis is to provide a mathematical explanation of this intriguing phenomenon. This is the first book in this area of research. The title is somewhat misleading. What is analyzed is not the usual simplex method that one sees in many papers and books in the literature, but a parametric variant of it called the ''shadow vertex method'' developed by the author. Of course, this criticism can be levelled against several publications in this area. As far as I know, no one has carried out an average analysis of the usual simplex method yet. What have been analyzed are parametric or self-dual parametric variants of the simplex method. Nobody knows what an appropriate probabilistic model is for real world linear programming problems. The problem analyzed in this book is of the form: find \(x\in R^ n\) that maximizes \(v^ Tx\), subject to \(a^ T_ ix\leq 1\), \(i=1\) to m, where \(m\geq n\); and the data, \(v,a_ 1,...,a_ m\) are all column vectors in \(R^ n\setminus \{0\}\), distributed independently, identically and symmetrically under rotations. There are two major weakeness of this probabilistic model. One is that it assigns probability zero to the set of degenerate problems. Many real world problems tend to have lots of zeros in the coefficient matrix, and to be degenerate. Another is that it makes the expected value of every data element to be zero, an unreasonable assumption for real world models, since we cannot get something for nothing. The analysis under more realistic probabilistic models is a field for future research. The book begins with an introductory chapter in which the motivation for carrying out the average analysis of pivotal methods for linear programming is clearly developed, and all the results obtained by researchers so far are summarized briefly. The next chapter describes the shadow vertex algorithm. This is followed by a lengthy treatment of the analysis of the average number of pivot steps, and proofs of polynomial boundedness of this number. The proofs are of course ''highly technical'' and involve many ''frightening quotients''. In a final chapter, the analysis has been extended to the linear program involving nonnegativity constraints on all the variables, in addition to those mentioned earlier. This book is a welcome addition to the mathematical literature on linear programming. After some years of very intense activity by several researchers, there is now a period of lull in this area. The publication of this book would hopefully awaken interest in this area and draw new researchers into it, so that the ultimate good of giving a satisfactory mathematical explanation of the good behavior of the simplex method on real world problems can be completed soon.