Presolver
From Wikimization
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 presolver is likely to check whether constant vector
is positive; for if so,
variable
can have only the trivial solution.
The effect of such tests is to reduce the problem dimensions.
Most commercial optimization problem solvers incorporate presolving. Particular reductions can be proprietary or invisible, while some control or selection may be given to a user. But all presolvers have the same motivation: to make an optimization problem smaller and (ideally) easier to solve. There is profit potential because a solver can then 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 solver software chronically exits with error or hangs.