Geometric Presolver example
From Wikimization
| 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> | ||
Current revision
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
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.