# Presolver

### From Wikimization

Line 10: | Line 10: | ||

Particular reductions performed can be proprietary, invisible, or some control or selection may be given to a user. | Particular reductions performed can be proprietary, invisible, or some control or selection may be given to a user. | ||

But all presolvers have the same motivation: to make an optimization problem smaller. | But all presolvers have the same motivation: to make an optimization problem smaller. | ||

- | There is profit in | + | There is profit in reducing problem size because, then, |

- | + | a solver can compete more effectively in the marketplace for large-scale problems. | |

We present a method for reducing variable dimension based upon geometry of constraints in the problem statement: | We present a method for reducing variable dimension based upon geometry of constraints in the problem statement: |

## Revision as of 01:10, 6 August 2011

# Introduction

*Presolving* conventionally means quick elimination of some variables and constraints prior to numerical solution of an optimization problem.
Presented with constraints for example,
a good presolver is likely to check whether constant vector were positive; for if it were,
then variable has only the trivial solution.
The overall effect of such tests is to make a problem dimensionally smaller.

Most commercial optimization problem solvers incorporate presolving. Particular reductions performed can be proprietary, invisible, or some control or selection may be given to a user. But all presolvers have the same motivation: to make an optimization problem smaller. There is profit in reducing problem size because, then, a solver can compete more effectively in the marketplace for large-scale problems.

We present a method for reducing variable dimension based upon geometry of constraints in the problem statement:

where is a matrix of predetermined dimension, represent the integers, the real numbers, and is some possibly empty index set.

The *caveat* to use of our proposed method for presolving is that it is not fast.
One would incorporate this method only when a problem is too big to be solved;
that is, when optimization problem solver software chronically exits with error, hangs,
or produces nonsense due to numerical error caused by dimension.