Geometric Presolver example
From Wikimization
(Difference between revisions)
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.'' | ||
[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> 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. | ||
- | A lower bound on | + | 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 | + | A lower bound on number of columns retained is <math>1104</math>. |
- | The present exercise is to determine | + | The present exercise is to determine whether any contemporary presolver can meet this lower bound. |
Revision as of 17:15, 11 April 2013
Assume that the following optimization problem is massive:
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 matrix having dimension and compatible vector. There exists a cardinality binary solution . Before attempting to find it, we presume to have no choice but to reduce dimension of the matrix prior to computing a solution.
A lower bound on number of rows of retained is .
A lower bound on number of columns retained is .
The present exercise is to determine whether any contemporary presolver can meet this lower bound.