Presolver
From Wikimization
Line 24: | Line 24: | ||
The ''caveat'' to use of our proposed method for presolving is that it is not fast. | 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; | One would incorporate this method only when a problem is too big to be solved; | ||
- | that is, when | + | that is, when optimization problem solver software chronically exits with error, hangs, |
or produces nonsense due to numerical error caused by dimension. | or produces nonsense due to numerical error caused by dimension. |
Revision as of 01:06, 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 making optimization problems smaller 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.