Geometric Presolver example

From Wikimization

(Difference between revisions)
Jump to: navigation, search
(New page: Assume that the following problem is massive: <center> <math>\begin{array}{rl}\mbox{find}&x\\ \mbox{subject to}&E\,x=t\\ &x\succeq_{}\mathbf{0}\end{array}</math> </center> The problem is p...)
Current revision (17:51, 5 May 2016) (edit) (undo)
 
(5 intermediate revisions not shown.)
Line 1: Line 1:
-
Assume that the following problem is massive:
+
Assume that the following optimization problem is massive:
<center>
<center>
-
<math>\begin{array}{rl}\mbox{find}&x\\
+
<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>
</center>
</center>
-
The problem is presumed solvable but not computable by any contemporary means.
+
The problem is presumed solvable but not computable by any contemporary means.<br>
-
The most logical strategy is to make the problem smaller.
+
The most logical strategy is to somehow make the problem smaller.<br>
 +
Finding a smaller but equivalent problem is called ''presolving.''
-
This file contains a real E matrix having dimension <math>533\times 2704</math> and compatible t vector. There exists a cardinality <math>36</math> binary solution <math>x</math>. Before attempting to find it, we have no choice but to reduce
+
[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> 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 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.

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