PRESOLVING IN LINEAR-PROGRAMMING

Most modern linear programming solvers analyze the LP problem before s ubmitting it to optimization. Some examples are the solvers WHIZARD (T omlin and Welch, 1983), OB1 (Lustig et al., 1994), OSL (Forrest and To mlin, 1992), Sciconic (1990) and CPLEX (Bixby, 1994). The purpose of t he presolve phase is to reduce the problem size and to discover whethe r the problem is unbounded or infeasible. In this paper we present a c omprehensive survey of presolve methods. Moreover, we discuss the rest oration procedure in detail, i.e., the procedure that undoes the preso lve. Computational results on the NETLIB problems (Gay, 1985) are repo rted to illustrate the efficiency of the presolve methods.