Presolver

From Wikimization

(Difference between revisions)
Jump to: navigation, search
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.
-
The smaller a problem, the less likely it is that a solver will encounter numerical problems due to finite precision arithmetic.
 
There is profit in making optimization problems
There is profit in making optimization problems
smaller because, then, a solver can compete more effectively in the marketplace for large-scale problems.
smaller because, then, a solver can compete more effectively in the marketplace for large-scale problems.

Revision as of 00:57, 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 LaTeX: a^{\rm T}x=0\,,~x\succeq0 for example, a good presolver is likely to check whether constant vector LaTeX: \,a were positive; for if it were, then variable LaTeX: \,x 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:

LaTeX: \begin{array}{rl}\mbox{minimize}_{x\in_{}\mathbb{R}^{^n}}&f(x)\\
<p>\mbox{subject to}&A_{}x=b\\
&x\succeq0\\
&x_{i\!}\in\mathbb{Z}~,\qquad i\in\mathcal{I}
</p>
\end{array}

where LaTeX: \,A is a matrix of predetermined dimension, LaTeX: \mathbb{Z} represent the integers, LaTeX: \reals the real numbers, and LaTeX: \mathcal{I} 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 an optimization problem solver chronically fails, hangs, or produces nonsense due to numerical error.

Personal tools