A novel linear optimization presolve technique based on Fourier-Motzkin elimination

Abstract Linear optimization solvers commonly employ presolve techniques to simplify and improve the solution characteristics of models before a simplex or interior point algorithm is used for solution. The Fourier-Motzkin elimination, a well-known mathematical algorithm for removing columns from linear inequality systems, has not been utilized as a presolve method in existing solvers due to its exponential row growth. We propose a novel presolve method based on the Fourier-Motzkin elimination, along with postsolve algorithms to recover the primal and dual optimal solutions. The algorithm controls row growth by judiciously selecting which columns to eliminate after computing an upper bound on model size prior to each variable elimination step. Our computational results demonstrate that the proposed presolve with Fourier-Motzkin elimination effectively reduces the number of rows, columns, and nonzero elements in general linear optimization problems. As a result, the algorithm reduces the total number of iterations of simplex methods in CPLEX. Additionally, when combined with the CPLEX presolve, our FME implementation leads to models smaller than those obtained by CPLEX presolve alone, leading to speed-ups for CPLEX’s primal simplex, dual simplex, and barrier methods.