Geometric Presolver example

From Wikimization

(Difference between revisions)
Jump to: navigation, search
Current revision (17:51, 5 May 2016) (edit) (undo)
 
(2 intermediate revisions not shown.)
Line 1: Line 1:
Assume that the following optimization problem is massive:
Assume that the following optimization problem is massive:
<center>
<center>
-
<math>\begin{array}{rl}\mbox{find}&x\in\mathbb{R}^n\\
+
<math>\begin{array}{rl}\mbox{ find}&x\in\mathbb{R}^n\\
\mbox{subject to}&E\,x=t\\
\mbox{subject to}&E\,x=t\\
&x\succeq_{}\mathbf{0}\end{array}</math>
&x\succeq_{}\mathbf{0}\end{array}</math>
Line 10: Line 10:
[http://www.convexoptimization.com/TOOLS/EAndy.mat This Matlab workspace file]
[http://www.convexoptimization.com/TOOLS/EAndy.mat This Matlab workspace file]
-
contains a real <math>E</math> matrix having dimension <math>533\times 2704</math> and compatible <math>t</math> vector. There exists a cardinality <math>36</math> binary solution <math>x</math>. Before attempting to find it, we presume to have no choice but to reduce dimension of the <math>E</math> matrix prior to computing a solution.
+
contains a real <math>E</math> matrix having dimension <math>533\times 2704</math> and compatible <math>t</math> vector. There exists a cardinality <math>36</math> solution <math>x</math>. Before attempting to find it, we presume to have no choice but to reduce dimension of the <math>E</math> matrix prior to computing a solution.
A lower bound on number of rows of <math>\,E\in\mathbb{R}^{533\times 2704}\,</math> retained is <math>217</math>.<br>
A lower bound on number of rows of <math>\,E\in\mathbb{R}^{533\times 2704}\,</math> retained is <math>217</math>.<br>
-
A lower bound on number of columns retained is <math>1104</math>.
+
A lower bound on number of columns retained is <math>1104</math>.<br>
 +
An eliminated column means it is evident that the corresponding entry in solution <math>x</math> must be <math>0</math>.
The present exercise is to determine whether any contemporary presolver can meet this lower bound.
The present exercise is to determine whether any contemporary presolver can meet this lower bound.

Current revision

Assume that the following optimization problem is massive:

LaTeX: \begin{array}{rl}\mbox{ find}&x\in\mathbb{R}^n\\ \mbox{subject to}&E\,x=t\\ &x\succeq_{}\mathbf{0}\end{array}

The problem is presumed solvable but not computable by any contemporary means.
The most logical strategy is to somehow make the problem smaller.
Finding a smaller but equivalent problem is called presolving.

This Matlab workspace file contains a real LaTeX: E matrix having dimension LaTeX: 533\times 2704 and compatible LaTeX: t vector. There exists a cardinality LaTeX: 36 solution LaTeX: x. Before attempting to find it, we presume to have no choice but to reduce dimension of the LaTeX: E matrix prior to computing a solution.

A lower bound on number of rows of LaTeX: \,E\in\mathbb{R}^{533\times 2704}\, retained is LaTeX: 217.
A lower bound on number of columns retained is LaTeX: 1104.
An eliminated column means it is evident that the corresponding entry in solution LaTeX: x must be LaTeX: 0.

The present exercise is to determine whether any contemporary presolver can meet this lower bound.

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