Geometric Presolver example
From Wikimization
| Line 13: | Line 13: | ||
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. | ||
Revision as of 13:06, 12 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 .
An eliminated column means it is evident that the corresponding entry in solution must be
.
The present exercise is to determine whether any contemporary presolver can meet this lower bound.