## IntroductionAny LP problem can be formulated as: Some of the simple bounds may be Define and Then the constraints of the LP are: We want a pre-solve procedure that would reduce the size of A without creating new non-zero terms. This also means that linear transformations are not allowed but changes to are. We make several passes through A and remove redundancies as and when they are detected. Some types of redundancies are easily understood and we will look at few of them. ## Redundancies in LP
When a row is empty, either the constraint is redundant or infeasible. When a column is empty, depending on the bounds on the variable and the objective function, the variable can either be fixed at its bounds or is unbounded. Column Singletons
A Removal of column singletons is very advantageous as they result in the removal of one variable and also one constraint. Another possibility is a Doubleton Equation combined with a column singleton : In this case, when is a column singleton we can modify bounds on such that feasible region is unchanged when bounds on are removed.
‘ Whenever our Presolve procedure detects a column singleton , we try to establish that it is For any feasible solution , it is easy to observe that . Thus, we have an implied free column singleton if -
Let and . Let's compute the quantities: Clearly, for any solution . Now if or , we have an unfeasible constraint. A forcing constraint is one where or . Here, the value of is fixed at its bounds according to the sign of and thus we can fix all variables that occur in the constraint. Removal of Forcing Constraints is highly advantageous as they we remove all variables that are structurally degenerate. We can also use this to detect more column singletons and we can determine for appropriate cases when and when or is finite. This is called the Dominated Constraint Procedure. Similarly there are concepts of Dominated Columns and Forcing Columns elaborately discussed in the paper by Andersen. ## Algorithm for LPRemove all fixed variables Repeat Check Rows Remove Row Singletons Remove Forcing Constraints
Dominated Constraints Remove all dominated constraints
Check Columns Remove all free, implied free column singletons Remove column singleton-double combinations
Dominated Columns Duplicate Rows Duplicate Columns
Until no reduction in last pass Remove all empty rows and columns
We also need to maintain a 'stack’ of presolve operations and undo a reduction such that, if the primal and dual solutions to the reduced problem are optimal and feasible, so is the solution to the restored problem. This constitutes a Post-solve procedure to recover solutions to the orginial problem, after we have solved the reduced LP. Each of the operations in pre-solve has a corresponding post-solve procedure whereby we 'unfix’ the fixed variable or constraint at each iteration. |