Presolve Analysis of Linear Programs Prior to Applying
an Interior Point Method
Jacek Gondzio
Several issues concerning an analysis of large and sparse linear
programming problems prior to solving them with an interior point
based optimizer are addressed in this paper. Three types of presolve
procedures are distinguished. Routines from the first class repeatedly
analyze an LP problem formulation: eliminate empty or singleton rows
and columns, look for primal and dual forcing or dominated constraints,
tighten bounds for variables and shadow prices or just the opposite,
relax them to find implied free variables. The second type of analysis
aims at reducing a fill-in of the Cholesky factor of the normal equations
matrix used to compute orthogonal projections and includes a heuristic
for increasing the sparsity of the LP constraint matrix and a technique
of splitting dense columns in it. Finally, routines from the third
class detect, and remove, different linear dependecies of rows and
columns in a constraint matrix.
Computational results on problems from the Netlib collection,
including some recently added infeasible ones, are given.
Technical Report 1994.3, Logilab,
HEC Geneva, Section of Management Studies, University of Geneva,
Bd. Carl-Vogt 102, 1211 Geneva, Switzerland, February 1994,
revised December 1994.