Presolver

From Wikimization

(Difference between revisions)
Jump to: navigation, search
(New page: =Introduction= ''Presolving'' conventionally means quick elimination of some variables prior to numerical solution of an optimization problem. Presented with constraints <math>a^{\rm T}x=...)
Line 3: Line 3:
''Presolving'' conventionally means quick elimination of some variables prior to numerical solution of an optimization problem.
''Presolving'' conventionally means quick elimination of some variables prior to numerical solution of an optimization problem.
Presented with constraints <math>a^{\rm T}x=0\,,~x\succeq0</math> for example,
Presented with constraints <math>a^{\rm T}x=0\,,~x\succeq0</math> for example,
-
a good presolver would check whether constant vector $a$ were positive; for if it were,
+
a good presolver would check whether constant vector <math>\,a</math> were positive; for if it were,
-
then variable $x$ has only the trivial solution.
+
then variable <math>\,x</math> has only the trivial solution.
The overall effect of such tests is to reduce variable dimension; to make a problem smaller.
The overall effect of such tests is to reduce variable dimension; to make a problem smaller.
Line 20: Line 20:
&x_{i\!}\in\mathbb{Z}~,\qquad i\in\mathcal{I}
&x_{i\!}\in\mathbb{Z}~,\qquad i\in\mathcal{I}
\end{array}</math></center>
\end{array}</math></center>
-
where <math>A</math> is a matrix of predetermined dimension, <math>\mathbb{Z}</math> represent the integers, <math>\reals</math> the real numbers,
+
where <math>\,A</math> is a matrix of predetermined dimension, <math>\mathbb{Z}</math> represent the integers, <math>\reals</math> the real numbers,
and <math>\mathcal{I}</math> is some possibly empty index set.
and <math>\mathcal{I}</math> is some possibly empty index set.

Revision as of 00:16, 6 August 2011

Introduction

Presolving conventionally means quick elimination of some variables prior to numerical solution of an optimization problem. Presented with constraints LaTeX: a^{\rm T}x=0\,,~x\succeq0 for example, a good presolver would 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 reduce variable dimension; to make a problem smaller.

Most commercial optimization problem solvers incorporate presolving. The 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. 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 smaller because, then, a solver can compete more effectively in the marketplace for large-scale problems.

We present a method for presolving 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.

Retrieved from "http://www.convexoptimization.com/wikimization/index.php/Presolver"
Personal tools