zbMATH — the first resource for mathematics

Simplex algorithms. (English) Zbl 0906.90122
Beasley, J. E. (ed.), Advances in linear and integer programming. Oxford: Clarendon Press. Oxf. Lect. Ser. Math. Appl. 4, 1-46 (1996).
In this survey paper, the authors briefly describe theoretical developments and solution methods of linear programs (LP) in exploiting the simplex method during the last 50 years. The main attention is devoted to solution methods for large (more than 5000 rows) LP problems by using the sparse simplex (SSX) algorithms. Main kinds of SSX algorithms are described: data structures (decomposition of data), preprocessing, starting basis (using an advanced basis), pricing (selection of an incoming variable), degeneracy (at least one of the basic variables is at their upper or lower bound), and sparse updates. Computational issues relating to SSX are covered. Two leading academic and commercial solvers are compared: FortMP and MINOS, and OSL and CPLEX, respectively. The authors calculate neither of them is better than the other relative to all parameters.
For the entire collection see [Zbl 0869.00020].
Reviewer: R.Lepp (Tallinn)

90C05 Linear programming
90C06 Large-scale problems in mathematical programming