The Simplex Method

LP problems are generally solved via the Simplex method. The standard Solver uses a straightforward implementation of the Simplex method to solve LP problems, when the Assume Linear Model box is checked in the Solver Options dialog. The Premium and Quadratic Solvers use an improved implementation of the Simplex method, when the Simplex or LP/Quadratic Solver is chosen from the Solver "engine" dropdown list in the Solver Parameters dialog. The memory required by this Simplex code increases with the number of variables times the number of constraints, regardless of the model's sparsity.

The Large-Scale LP Solver uses a far more sophisticated implementation of the Simplex method, which fully exploits sparsity in the LP model to save time and memory. To cope with potential numerical instabilities, the Large-Scale LP Solver uses techniques such as automatic scaling, matrix factorization using the LU decomposition with the Bartels-Golub update, steepest-edge pivoting strategies, and dynamic Markowitz refactorization. These same techniques often result in much faster solution times -- making it practical to solve LP problems with thousands of variables and constraints.