Presolver

From Wikimization

(Difference between revisions)
Jump to: navigation, search
m (→Introduction)
Line 3: Line 3:
''Presolving'' conventionally means quick elimination of some variables and constraints prior to numerical solution of an optimization problem.
''Presolving'' conventionally means quick elimination of some variables and constraints 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 is likely to check whether constant vector <math>\,a</math> were positive; for if it were,
+
a presolver is likely to check whether constant vector <math>\,a</math> is positive; for if so,
-
then variable <math>\,x</math> has only the trivial solution.
+
variable <math>\,x</math> can have only the trivial solution.
-
The overall effect of such tests is to make a problem dimensionally smaller.
+
The effect of such tests is to reduce the problem dimensions.
Most commercial optimization problem solvers incorporate presolving.
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.
+
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.
+
But all presolvers have the same motivation: to make an optimization problem smaller
-
There is profit in reducing problem size because, then,
+
and (ideally) easier to solve.
-
a solver can compete more effectively in the marketplace for large-scale problems.
+
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:
We present a method for reducing variable dimension based upon geometry of constraints in the problem statement:
-
<center><math>\begin{array}{rl}\mbox{minimize}_{x\in_{}\mathbb{R}^{^n}}&f(x)\\
+
<center>
-
\mbox{subject to}&A_{}x=b\\
+
<math>
-
&x\succeq0\\
+
\begin{array}{rl}
-
&x_{j\!}\in\mathbb{Z}~,\qquad j\in\mathcal{J}
+
\mbox{minimize}_{x\in_{}\mathbb{R}^{^n}} &f(x)
-
\end{array}</math></center>
+
\\ \mbox{subject to} &A_{}x=b
 +
\\ &x\succeq0
 +
\\ &x_{j\!}\in\mathbb{Z}~,\qquad j\in\mathcal{J}
 +
\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{J}</math> is some possibly empty index set.
and <math>\mathcal{J}</math> is some possibly empty index set.
Line 24: Line 30:
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 optimization problem solver software chronically exits with error, hangs,
+
that is, when solver software chronically exits with error or hangs.
-
or produces nonsense due to numerical error caused by dimension.
+

Revision as of 11:23, 7 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 presolver is likely to check whether constant vector LaTeX: \,a is positive; for if so, variable LaTeX: \,x 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: 

 LaTeX: 
   \begin{array}{rl}
       \mbox{minimize}_{x\in_{}\mathbb{R}^{^n}} &f(x)
   \\ \mbox{subject to} &A_{}x=b
   \\                                  &x\succeq0
   \\                                  &x_{j\!}\in\mathbb{Z}~,\qquad j\in\mathcal{J}
   \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{J} 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.

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