| Article ID: | iaor19971090 |
| Country: | Netherlands |
| Volume: | 71 |
| Issue: | 2 |
| Start Page Number: | 221 |
| End Page Number: | 245 |
| Publication Date: | Dec 1995 |
| Journal: | Mathematical Programming (Series A) |
| Authors: | Andersen Erling D., Andersen Knud D. |
Most modern linear programming solvers analyze the LP problem before submitting it to optimization. Some examples are the solvers WHIZARD (Tomlin and Welch) OB1 (Lustig et al.), OSL (Forrest and Tomlin), Sciconic and CPLEX (Bixby). The purpose of the presolve phase is to reduce the problem size and to discover whether the problem is unbounded or infeasible. In this paper the authors present a comprehensive survey of presolve methods. Moreover, they discuss the restoration procedure in detail, i.e., the procedure that undoes the presolve. Computational results on the NETLIB problems (Gay) are reported to illustrate the efficiency of the presolve methods.