Presolve Methods

Presolve methods are important in solving LPs, as they reduce the size of the problem and discover whether an LP is unbounded or infeasible. Presolve methods are used prior to the application of an LP algorithm in order to: (i) eliminate redundant constraints, (ii) fix variables, (iii) transform bounds of single structural variables, and (iv) reduce the number of variables and constraints by eliminations. This chapter presents eleven presolve methods used prior to the execution of an LP algorithm: (i) eliminate zero rows, (ii) eliminate zero columns, (iii) eliminate singleton equality constraints, (iv) eliminate kton equality constraints, (v) eliminate singleton inequality constraints, (vi) eliminate dual singleton inequality constraints, (vii) eliminate implied free singleton columns, (viii) eliminate redundant columns, (ix) eliminate implied bounds on rows, (x) eliminate redundant rows, and (xi) make coefficient matrix structurally full rank. Each method is presented with: (i) its mathematical formulation, (ii) a thorough numerical example, and (iii) its implementation in MATLAB. In addition, we discuss how to transform a solution back in terms of the original variables and constraints of the problem (postsolve). Finally, a computational study on benchmark LPs is performed. The aim of the computational study is twofold: (i) compare the execution time and the reduction to the problem size of the aforementioned presolve methods, and (ii) investigate the impact of preprocessing prior to the application of LP algorithms. The execution time and the number of iterations with and without preprocessing are presented.